c++如何实现图的深度优先搜索_c++ DFS算法代码【算法】

最简DFS遍历用std::vector邻接表和递归实现，核心是visited数组防重访、递归访问未访邻点；图不连通时需遍历所有起点调用DFS。

用 std::vector 和递归写最简 DFS 遍历

标准 DFS 的核心是“走到不能走为止，再回退”。c++ 里用邻接表 + 递归最直观，不需要手动维护栈。关键点不是写得短，而是避免重复访问和栈溢出。

• 图用 std::vector<:vector>> 存储，graph[u] 是节点 u 的所有邻接点
• 必须用 std::vector 记录访问状态，不能靠节点值是否为 -1 或 0 来判断（数值可能合法）
• 递归函数参数只需传当前节点 u，无需传父节点（无向图需额外处理环，但基础 DFS 不需要）
• 如果图不连通，主逻辑要遍历所有未访问节点调用 DFS，不能只从 0 开始

void dfs(int u, const vector>& graph, vector& visited) {     visited[u] = true;     for (int v : graph[u]) {         if (!visited[v]) {             dfs(v, graph, visited);         }     } }

非递归 DFS 必须用 stack 模拟调用栈

递归 DFS 在深图上容易爆栈（比如链状图 1→2→3→…→10⁵），这时必须手写栈。注意：非递归版本的访问顺序和递归版一致，但“何时标记已访问”有坑。

• 错误做法：在 pop() 后才设 visited[u] = true → 同一节点可能被多次压入栈
• 正确做法：在 push() 前就标记 visited[u] = true，确保每个节点只入栈一次
• 压栈顺序影响遍历路径（比如先压右子节点还是左子节点），但不影响连通性判断
• 用 std::stack 即可，不必存额外信息；若需记录深度或父节点，才扩展为 Struct

void dfs_iterative(int start, const vector>& graph, vector& visited) {     stack st;     visited[start] = true;     st.push(start);     while (!st.empty()) {         int u = st.top(); st.pop();         for (int v : graph[u]) {             if (!visited[v]) {                 visited[v] = true;                 st.push(v);             }         }     } }

DFS 判环时无向图和有向图处理方式不同

单纯遍历不关心环，但做拓扑排序、强连通分量或检测图类型时，环检测是刚需。无向图和有向图的 DFS 环判定逻辑完全不同，混用会漏判或误判。

• 无向图：跳过「父节点」即可。递归时传 parent 参数，遇到未访问邻居且不是父节点，就成环
• 有向图：必须用三色标记法（unvisited/visiting/visited），仅靠 visited 数组无法区分跨分支边和回边
• 错误示例：对有向图只用二值 visited，把 A→B→C→A 里的 C→A 当成已访问而忽略，实际是环
• 三色法中，遇到 visiting 状态的节点即存在环，此时可提前返回

用 DFS 求连通分量数量或最大连通块大小

这是 DFS 最常见的变体应用。核心不是改算法结构，而是调整「计数时机」和「作用域」。

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

• 每次新进入未访问节点就启动一次 DFS，调用次数 = 连通分量数
• 在递归 DFS 内部用局部变量累加当前连通块大小，返回该值；主循环中取最大值
• 不要在全局变量里累加——多个连通块会互相污染
• 若图是带权的（如节点有权重），把累加对象换成权重和即可，逻辑不变
• 注意：节点编号不一定从 0 连续，要用 map 替代 vector，否则越界

DFS 的边界细节比想象中多：邻接表初始化是否包含自环、输入是否有重边、图是 0-indexed 还是 1-indexed、是否要求输出路径而非仅判断可达——这些都会让同一份模板代码在不同题目里失效。