深入理解图的迭代式深度优先遍历（DFS）：从原理到实践

2026-02-17 23:59:23 0条评论 1次阅读 0人点赞

在这篇文章中，我们将深入探讨图论中一个至关重要的算法——深度优先搜索（DFS）。虽然你可能已经熟悉了递归式的 DFS 实现，但在实际工程面试和高性能系统设计中，迭代式 DFS 往往因其对内存的精确控制而更受青睐。我们将一起解开迭代实现的神秘面纱，看看它是如何利用显式栈来模拟递归过程的，以及为什么在处理邻居节点时，我们需要反直觉地“逆序”操作。

1. 核心概念：什么是迭代式 DFS？

首先，让我们回顾一下基本问题。给定一个有向图，我们的目标是从某个起始节点（通常是节点 0）出发，沿着图的边缘尽可能深地搜索，直到没有未访问的邻接点时才回溯。

> 注意： 遍历顺序取决于我们选择相邻顶点的策略。为了保持与邻接表（如 [1, 2, 3]）一致的“从左到右”的遍历顺序，我们在迭代实现中需要一点特殊的技巧。

#### 为什么要选择迭代而不是递归？

在深入代码之前，你必须明白迭代法的核心价值：

  • 控制力：递归使用的是系统调用栈，当图非常深时，可能会导致栈溢出错误。而迭代法使用的是我们手动管理的栈，受限于堆内存，通常能处理更深的数据结构。
  • 状态管理：迭代法允许我们在循环中精确控制何时访问节点、何时压栈，这对于一些复杂的状态记录问题非常有利。

我们的核心思路非常直观：模拟递归。我们将起始节点压入一个显式的栈结构中。只要栈不为空，我们就不断地从栈顶弹出元素进行处理。这个过程就像是在整理一叠文件，你总是先处理最上面的那一份。

2. 算法详解：逆序压栈的奥秘

这是初学者最容易困惑的地方，也是本文的重点。栈遵循 LIFO（后进先出） 原则。

假设我们有一个节点 INLINECODEa1167f3f，它的邻接表是 INLINECODEe3f6bad9。如果我们希望先访问 INLINECODE8de31317，再访问 INLINECODE5cb2ad4b（即从左到右），我们必须问自己：谁应该最后进栈？

  • 因为最后进栈的元素会最先被弹出（栈顶），所以为了让 INLINECODE80e16881 先被处理，INLINECODE85ddb59d 必须最后进栈。
  • 因此，我们需要按 逆序 将邻接点压入栈中：先压 INLINECODEf78b129f，再压 INLINECODE8490922f。这样，1 就会位于栈顶，从而被优先访问。

#### 逐步操作指南

  • 初始化：创建一个空栈 INLINECODEdbda35e8，并将源节点 INLINECODE106dc648 压入栈中。同时，初始化一个 visited 数组来防止重复访问。
  • 循环处理：只要栈不为空，执行以下操作：

* 弹出：移除栈顶元素 node。

* 检查：如果 node 已经被访问过，直接跳过（continue）。这是一种处理冗余的高效方式。

* 访问：将 node 标记为已访问，并将其加入结果列表。

* 逆序压栈：遍历 node 的所有邻接点。为了保持原有的访问顺序，我们需要 从右向左 遍历邻接表，将未访问的节点压入栈中。

3. 代码实现与解析

为了确保你能在各种技术场景下应用这一算法，我们提供了 C++、Java、Python 和 JavaScript 的完整实现。请注意代码中的注释，它们解释了关键步骤。

#### C++ 实现：高效且严谨

C++ 的 STL 提供了高效的 INLINECODE8360c4cb 和 INLINECODEe7f31799，非常适合处理这类图论问题。

// C++ program to perform Iterative 
// Depth First Traversal of Graph
#include 
using namespace std;

// 参数：邻接表引用
// 返回：DFS 遍历结果向量
vector dfs(vector<vector>& adj) {
    int n = adj.size();
    
    // visited 数组用于跟踪节点状态，防止重复访问
    vector visited(n, false);
    // res 用于存储遍历顺序
    vector res;
    
    // 初始化栈，从节点 0 开始 DFS
    stack st;
    st.push(0);
    
    while (!st.empty()) {
        // 获取栈顶元素并将其弹出
        int node = st.top();
        st.pop();
        
        // 如果节点已被访问，跳过当前循环
        // 这处理了图中存在环的情况，避免了死循环
        if (visited[node]) {
            continue;
        }
        
        // 标记当前节点为已访问
        visited[node] = true;
        res.push_back(node);
        
        // 关键步骤：逆序处理邻接点
        // 因为栈是后进先出 (LIFO)，为了保持邻接表的顺序，
        // 我们必须从右向左将邻接点压入栈中。
        int size = adj[node].size();
        for (int i = size - 1; i >= 0; i--) {
            int v = adj[node][i];
            // 只有未被访问的节点才需要压栈
            if (!visited[v]) st.push(v);
        }
    }
    
    return res;
}

int main() {
    // 示例图：0->1, 0->2, 1->2, 2->0, 2->3
    vector<vector> adj = 
    {{1, 2}, {2}, {0, 3}, {3}};
    
    vector res = dfs(adj);
    for (auto node: res) cout << node << " ";
    cout << endl;

    return 0;
}

#### Java 实现：面向对象的稳健性

在 Java 中，我们使用 INLINECODE7399db20 来模拟动态数组，并利用 INLINECODE8756905e 类（或 ArrayDeque）来实现迭代逻辑。注意 Java 的语法糖在处理列表时非常方便。

// Java program to perform Iterative 
// Depth First Traversal of Graph
import java.util.*;

class GfG {

    // Start DFS from node 0.
    static ArrayList dfs(ArrayList<ArrayList> adj) {
        int n = adj.size();
        
        boolean[] visited = new boolean[n];
        ArrayList res = new ArrayList();
        
        Stack st = new Stack();
        st.push(0);
        
        while (!st.isEmpty()) {
            int node = st.pop();
            
            // 检查是否已访问，防止重复处理
            if (visited[node]) {
                continue;
            }
            
            // 标记访问并记录结果
            visited[node] = true;
            res.add(node);
            
            // 获取当前节点的邻接表大小
            // 逆序遍历以保证栈顶是正确的下一个节点
            int size = adj.get(node).size();
            for (int i = size - 1; i >= 0; i--) {
                int v = adj.get(node).get(i);
                if (!visited[v]) st.push(v);
            }
        }
        
        return res;
    }

    public static void main(String[] args) {
        // 构建测试数据
        ArrayList<ArrayList> adj = new ArrayList();
        adj.add(new ArrayList(Arrays.asList(1, 2)));
        adj.add(new ArrayList(Arrays.asList(2)));
        adj.add(new ArrayList(Arrays.asList(0, 3)));
        adj.add(new ArrayList(Arrays.asList(3)));
        
        ArrayList res = dfs(adj);
        for (int node : res) {
            System.out.print(node + " ");
        }
        System.out.println();
    }
}

#### Python 实现：简洁与可读性

Python 的列表不仅可以用作动态数组，还可以直接用作栈（使用 INLINECODEaac6b815 和 INLINECODE57972c0f）。这使得代码极其简洁。我们使用 reversed() 函数来优雅地处理逆序需求。

# Python program to perform Iterative
# Depth First Traversal of Graph

def dfs(adj):
    n = len(adj)
    
    visited = [False] * n
    res = []
    
    # Start DFS from node 0
    stack = [0]
    
    while stack:
        # 弹出栈顶元素
        node = stack.pop()
        
        # 如果已访问则跳过
        if visited[node]:
            continue
        
        # 标记并记录
        visited[node] = True
        res.append(node)
        
        # 关键技巧：
        # 使用 reversed 函数反转邻接表，确保从左到右的访问顺序。
        # 例如：原邻接表 [1, 2] -> 反转后压栈顺序 -> 栈顶是 1。
        for v in reversed(adj[node]):
            if not visited[v]:
                stack.append(v)
                
    return res

if __name__ == "__main__":
    # 测试用例
    adj = [[1, 2], [2], [0, 3], [3]]
    res = dfs(adj)
    print(" ".join(map(str, res)))

#### C# 实现：强类型系统的应用

C# 提供了非泛型的 INLINECODE34095a8a，但在现代开发中，我们通常推荐使用泛型 INLINECODEcb225a55 以确保类型安全并减少拆箱装箱的开销。

// C# program to perform Iterative
// Depth First Traversal of Graph
using System;
using System.Collections.Generic;

class GfG {

    // Start DFS from node 0.
    static List dfs(List<List> adj) {
        int n = adj.Count;
        
        bool[] visited = new bool[n];
        List res = new List();
        
        Stack st = new Stack();
        st.Push(0);
        
        while (st.Count > 0) {
            int node = st.Pop();
            
            if (visited[node]) {
                continue;
            }
            
            visited[node] = true;
            res.Add(node);
            
            // 逆序遍历邻接表以维持 DFS 顺序
            int size = adj[node].Count;
            for (int i = size - 1; i >= 0; i--) {
                int v = adj[node][i];
                if (!visited[v]) st.Push(v);
            }
        }
        
        return res;
    }

    public static void Main(string[] args) {
        List<List> adj = new List<List>();
        adj.Add(new List{1, 2});
        adj.Add(new List{2});
        adj.Add(new List{0, 3});
        adj.Add(new List{3});
        
        List res = dfs(adj);
        foreach (int node in res) {
            Console.Write(node + " ");
        }
        Console.WriteLine();
    }
}

#### JavaScript 实现：Web 开发的必备技能

在现代前端开发或 Node.js 环境中，处理 JSON 格式的图结构非常常见。JavaScript 的数组原生的 INLINECODE264fa7b1 和 INLINECODE4becfd28 方法完美支持栈操作。

// JavaScript program to perform Iterative
// Depth First Traversal of Graph

class Solution {
    dfs(adj) {
        const n = adj.length;
        
        // 使用数组模拟栈
        let visited = new Array(n).fill(false);
        let res = [];
        let stack = [0];
        
        while (stack.length > 0) {
            let node = stack.pop();
            
            if (visited[node]) {
                continue;
            }
            
            visited[node] = true;
            res.push(node);
            
            // 获取邻接点并逆序遍历
            let neighbors = adj[node];
            for (let i = neighbors.length - 1; i >= 0; i--) {
                let v = neighbors[i];
                if (!visited[v]) {
                    stack.push(v);
                }
            }
        }
        
        return res;
    }
}

// Driver code
const adj = [[1, 2], [2], [0, 3], [3]];
const sol = new Solution();
const res = sol.dfs(adj);
console.log(res.join(" "));

4. 复杂度分析：性能考量

在面试或系统设计中，分析算法的效率是必不可少的一环。

  • 时间复杂度：O(V + E)

* V 是顶点数，E 是边数。

* 我们每个节点最多被访问一次（标记为 visited 时）。

* 我们检查了每条边两次（在有向图中是出边检查，在邻接表遍历中就是 adj[node].size() 的总和）。这是图算法的最优时间复杂度，因为我们至少需要查看每个节点和每条边一次。

  • 空间复杂度：O(V)

* 主要消耗来自于显式栈和 visited 数组。

* 在最坏的情况下（例如一条直链状的图 0 -> 1 -> 2 -> ... -> V-1），栈中可能会同时存储所有的顶点。

* 这与递归 DFS 的空间复杂度一致，但迭代法避免了递归深度过大导致的调用栈崩溃风险。

5. 常见误区与最佳实践

在我们结束之前，我想分享几个在实际开发中容易遇到的坑：

  • 忘记检查 INLINECODEce91ddc8 状态：在压栈之前或者在弹出之后，必须检查 INLINECODE3b57e821。如果在弹出时才检查（如我们的代码所示），你可能会在栈中留下冗余节点，但这能保证逻辑正确。如果在压栈时就检查，可以减少栈的大小，但要注意更新时机。本示例中采用“出栈时检查”的策略，配合 continue 语句，代码逻辑最为清晰且鲁棒性最好。
  • 忽略逆序压栈：这是最常见的错误。如果你直接按照 INLINECODEc88af89a 的顺序压栈，你的 DFS 顺序将变成 INLINECODEece73e57。虽然这仍然是合法的 DFS，但在需要严格匹配测试用例或特定逻辑（如拓扑排序）时，这会导致错误。
  • 图的连通性：本文的代码假设从节点 0 出发可以到达图中的所有其他节点。如果图是不连通的（例如有两个独立的孤岛），你需要在外层套一个循环，遍历 visited 数组，对每个未访问的节点都重新调用一次 DFS 逻辑。

总结

通过这篇文章，我们不仅掌握了如何用迭代的方式实现深度优先搜索，更重要的是，我们理解了显式栈的工作机制以及 LIFO 结构如何影响我们的遍历顺序。与递归法相比，迭代法给了我们更多的控制权，是解决复杂图论问题和避免栈溢出的强力工具。

希望你在下次遇到“图的遍历”问题时，能自信地写出这份迭代 DFS 代码！继续加油，探索更多算法的奥秘吧。

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/54399.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年