c++中如何实现深度优先搜索_c++ DFS算法图论遍历方法【详解】

DFS递归必须用visited标记防环，且需在递归前设true；迭代版用stack并倒序压入保序；判断环需区分无向图（传parent）和有向图（用recStack）；邻接表优选vector以提升缓存性能。

DFS 递归实现必须处理访问标记

不加访问标记的 DFS 在图中会无限循环，尤其遇到环或无向图边双向存在时。用 vector 或 unordered_set 记录已访问节点是硬性要求。

• visited[i] = true 必须在进入递归前设置，不能放在递归调用之后
• 对邻接表 vector> graph，遍历 graph[u] 中每个 v 前先检查 !visited[v]
• 无向图中，即使边只存一次（如 u→v），v→u 仍可能通过其他路径抵达，所以标记不可省

迭代版 DFS 要用 stack 模拟调用栈

手动维护栈比递归更可控，适合防止爆栈或需记录路径/层数的场景。注意：栈中只存节点编号，不存边或状态标志。

• 入栈顺序影响遍历结果——若按邻接表原始顺序压栈，出栈是逆序；想保持左→右顺序，应倒序压入
• 每次 stack.pop() 后立即设 visited[u] = true，避免重复入栈
• 不要在循环内对当前节点的邻居反复 push/pop，应一次性遍历并过滤已访问节点

void dfs_iterative(int start, const vector>& graph) {
    vector visited(graph.size(), false);
    stack stk;
    stk.push(start);

    while (!stk.empty()) {
        int u = stk.top();
        stk.pop();
        if (visited[u]) continue;
        visited[u] = true;
        // 处理节点 u：打印、存路径、更新状态等

        // 倒序压入，保证邻接表顺序被保留（可选）
        for (auto it = graph[u].rbegin(); it != graph[u].rend(); ++it) {
            if (!visited[*it]) {
                stk.push(*it);
            }
        }
    }
}

DFS 判断连通性与找环的逻辑差异

同一套 DFS 框架，仅靠参数和返回值设计就能区分用途。关键在如何定义“回边”和是否允许父节点干扰判断。

• 判断无向图是否有环：传入 parent 参数，跳过 v == parent 的边；发现未访问却已入栈的邻居即为环
• 判断有向图环：需额外 recStack 数组记录当前递归路径上的节点，而非仅 visited
• 连通分量计数：每启动一次未访问节点的 DFS，components++，适用于非连通图

vector> 邻接表比 map> 更快但不支持稀疏大编号

下标连续且范围已知（如节点编号 0~n−1）时，vector 是首选；若节点编号稀疏（如 1e9 级别 ID），必须用哈希结构，但 DFS 本身开销会上升。

• vector> graph(n) 支持 O(1) 随机访问，push_back 平摊 O(1)
• 用 map 或 unordered_map 时，每次 graph[u].count(v)

  

  是 O(log k) 或均摊 O(1)，但整体常数更大
• DFS 中反复调用 graph[u].size() 和遍历，vector 的 cache 局部性明显更好

真正容易被忽略的是：递归 DFS 的函数参数传递方式（值传 vs 引用）、迭代 DFS 中栈元素是否去重、以及有向图环检测时 recStack 的置位/复位时机——这些细节不写错，算法才能稳定输出正确结果。