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

- 日理万妓 2024-02-20 08:15 8阅读 0赞

## 深度优先搜索（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结束后，我们需要将这个节点的状态重置为未访问。