深度优先搜索（DFS）的基础理解与实现

GeekLiHua

发布于 2025-01-21 13:10:25

4000

文章被收录于专栏：JavaJava

深度优先搜索（DFS）的基础理解与实现

深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。这种算法会尽可能深地搜索树的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

下面是一个简单的DFS实现：

#include<bits/stdc++.h>
using namespace std;
const int N = 10;
int n;
int st[N];
int a[N];

void dfs (int u)
{
    if (u == n)
    {
        for (int i = 0; i < n; ++ i) cout << a[i] << " ";
        puts("");
        return;
    }
    for (int i = 1; i <= n; ++ i)
    {
        if (!st[i])
        {
            a[u] = i;
            st[i] = true;
            dfs (u + 1);
            st[i] = false;
        }
    }
}
int main()
{
    cin >> n;
    dfs (0);
    return 0;
}

在这段代码中，我们定义了一个数组st来记录每个节点是否被访问过，a数组用来记录每次DFS搜索的结果。dfs函数是DFS的主体部分，参数u代表当前正在访问的节点。

在dfs函数中，首先检查当前节点是否是目标节点（u == n），如果是，则打印出当前的搜索结果并返回。如果不是，我们就遍历所有的节点，对于每个未被访问过的节点，我们将其标记为已访问，然后从这个节点开始进行DFS，DFS结束后，我们需要将这个节点的状态重置为未访问。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-01-20，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历