C++如何实现深度优先搜索 C++深度优先搜索的代码实现

穿越時空

发布时间：2025-06-25 11:55:01

1132人浏览过

来源于php中文网

原创

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

C++如何实现深度优先搜索 C++深度优先搜索的代码实现

深度优先搜索（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函数到达一个没有未访问邻居的节点时，函数执行完毕，就像你走到了迷宫的死胡同。这时，函数会从调用栈中弹出，回到上一个路口，继续搜索。

立即学习“C++免费学习笔记（深入）”；

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

触发式加载精美特效企业网站源码1.0.0

触发式加载精美特效企业网站源码使用jquery实现了很多精美的触发式加载特效，网站首页在随着访客的滚动条滚动过程中会出现很多触发式加载的特殊效果，让这个网站的风格瞬间显得非常的高大上，让你的企业品牌在访客心中留下更深的影响。当然，我们在使用jquery特效的同时也要注意程序对搜索引擎的友好型，所以这一点儿作者也有考虑到，已经尽可能的对js和css脚本进行精简和优化，尽可能的加快网站加载速度，同时也

下载

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

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

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