C++实现深度优先搜索方法详解

C++中DFS递归调用栈可通过迷宫比喻理解，每次进入新节点即将其信息压入栈，回溯时弹出。调用栈深度反映搜索深度，过深可能导致栈溢出。处理环的方法是使用visited数组标记已访问节点，避免重复访问；另一种方法是采用三种状态（未访问、正在访问、已访问）来检测环。DFS与BFS的主要区别在于搜索方式：1.DFS尽可能深入探索路径，适合路径查找和环检测；2.BFS逐层扩展，适合寻找最短路径和连通分量。选择DFS的情况包括需要找到任意路径、检测图环或内存受限的场景，而BFS更适合需最短路径或完全遍历的问题。

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

#include 
#include 

using namespace std;

void dfs(int node, vector>& adj, vector& visited) {
    visited[node] = true;
    cout << node << " ";

    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, adj, visited);
        }
    }
}

int main() {
    int n, m; // n: 节点数量, m: 边的数量
    cin >> n >> m;

    vector> adj(n); // 邻接表
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u); // 如果是无向图
    }

    vector visited(n, false);

    // 从节点0开始DFS
    dfs(0, adj, visited);
    cout << endl;

    return 0;
}

如何理解C++中DFS递归的调用栈？

想象一下，你在一座迷宫里，手里拿着一根线。你总是沿着一条路走到底，如果走到尽头，就沿着线退回上一个路口，再选择另一条路。这个“线”就是调用栈。

每次调用dfs函数，就像你在迷宫里走到了一个新的路口。这个路口的信息（节点编号、邻接表、访问标记）都会被压入调用栈。当dfs函数到达一个没有未访问邻居的节点时，函数执行完毕，就像你走到了迷宫的死胡同。这时，函数会从调用栈中弹出，回到上一个路口，继续搜索。

调用栈的深度反映了DFS搜索的深度。如果图非常深，调用栈可能会变得很大，导致栈溢出。

如何处理C++ DFS中的环？

在图中存在环的情况下，DFS可能会陷入无限循环。解决这个问题的方法是使用一个visited数组来跟踪已经访问过的节点。在上面的代码示例中，visited[node] = true;这一行代码就是用来标记节点已经被访问过。在递归调用dfs函数之前，会检查邻居节点是否已经被访问过if (!visited[neighbor])，如果已经被访问过，则跳过该邻居节点，避免无限循环。

另一种方法是使用三种状态来标记节点：未访问、正在访问、已访问。当第一次遇到一个节点时，将其标记为“正在访问”。当该节点的所有邻居都访问完毕后，将其标记为“已访问”。如果在DFS过程中遇到一个“正在访问”的节点，则说明存在环。

C++ DFS与BFS的区别是什么？什么时候应该使用DFS？

DFS和BFS都是图遍历算法，但它们的搜索方式不同。DFS像是一个“深度优先”的探险家，总是尽可能深地探索一条路径，直到无法继续前进才回溯。而BFS则像是一个“广度优先”的侦察兵，从起点开始，一层一层地向外扩展，先访问所有距离起点为1的节点，再访问所有距离起点为2的节点，以此类推。

选择DFS还是BFS取决于具体的问题：

• DFS的优点：
  • 更容易实现。
  • 占用空间更少（在某些情况下）。
  • 可以用于检测环。
  • 可以用于解决路径搜索问题，例如迷宫求解。
• BFS的优点：
  • 可以找到最短路径（在无权图中）。
  • 可以用于寻找连通分量。

如果问题需要找到最短路径，或者需要遍历图的所有节点，BFS通常是更好的选择。如果问题只需要找到一条路径，或者需要检测环，DFS可能更适合。 此外，如果图非常深，BFS可能会占用更多的内存，因为需要存储所有已访问节点的队列。在这种情况下，DFS可能更有效。