《Hello 算法》图的遍历：BFS 与 DFS 的实现原理、多语言代码与复杂度分析

本文基于《Hello 算法》（hello-algo）仓库的图论章节文档与配套源码，系统讲解图的两种基本遍历方式——广度优先遍历（BFS）与深度优先遍历（DFS）：从核心思想、算法步骤到可运行的多语言参考实现，并给出时间/空间复杂度推导与遍历序列不唯一性的讨论。读完后，你能够独立写出并验证一个无向图的 BFS/DFS 实现，理解 visited 哈希集合、队列/递归这两种驱动结构在算法中的分工。

树与图：遍历是搜索的特例

树代表的是“一对多”的关系，而图具有更高的自由度，可以表示任意的“多对多”关系。因此，树可以看作图的一种特例，树的遍历操作也是图的遍历操作的一种特例。

图和树都需要应用搜索算法来实现遍历操作。图的遍历方式分为两种：

• 广度优先遍历（BFS）：由近及远，一层层向外扩张；
• 深度优先遍历（DFS）：优先走到底，无路可走再回头。

在仓库中，两者的实现都位于 codes/<语言>/chapter_graph/ 目录下（如 graph_bfs.py、graph_dfs.py），并统一建立在邻接表数据结构之上，即 GraphAdjList 类。以 Python 版为例，邻接表内部是一个 dict[Vertex, list[Vertex]]，key 为顶点、value 为该顶点的所有邻接顶点，这使得“获取指定顶点的所有邻接顶点”可以一次查表完成——这正是 BFS/DFS 实现的前提。

广度优先遍历（BFS）

核心思想：由近及远

广度优先遍历是一种由近及远的遍历方式：从某个节点出发，始终优先访问距离最近的顶点，并一层层向外扩张。 从左上角顶点出发，首先遍历该顶点的所有邻接顶点，然后遍历下一个顶点的所有邻接顶点，以此类推，直至所有顶点访问完毕。

算法步骤与队列

BFS 通常借助队列实现。队列“先入先出”的性质，与 BFS “由近及远”的思想异曲同工。算法流程如下：

1. 将遍历起始顶点 startVet 加入队列，并开启循环。
2. 在循环的每轮迭代中，弹出队首顶点并记录访问，然后将该顶点的所有邻接顶点加入到队列尾部。
3. 循环步骤 2，直到所有顶点被访问完毕后结束。

为了防止重复遍历顶点，需要借助一个哈希集合 visited 记录哪些顶点已被访问。

提示：哈希集合可以看作一个只存储 key 而不存储 value 的哈希表，它可以在 $O(1)$ 时间复杂度下进行 key 的增删查改操作。根据 key 的唯一性，哈希集合通常用于数据去重等场景。

Python 参考实现

下面是仓库中 graph_bfs.py 的核心代码：

def graph_bfs(graph: GraphAdjList, start_vet: Vertex) -> list[Vertex]:
    """广度优先遍历"""
    # 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
    res = []                          # 顶点遍历序列
    visited = setVertex  # 哈希集合，记录已被访问的顶点
    que = dequeVertex     # 队列用于实现 BFS
    # 以顶点 start_vet 为起点，循环直至访问完所有顶点
    while len(que) > 0:
        vet = que.popleft()          # 队首顶点出队
        res.append(vet)              # 记录访问顶点
        # 遍历该顶点的所有邻接顶点
        for adj_vet in graph.adj_list[vet]:
            if adj_vet in visited:
                continue             # 跳过已被访问的顶点
            que.append(adj_vet)      # 只入队未访问的顶点
            visited.add(adj_vet)     # 标记该顶点已被访问
    return res

从源码结构看，这里有一个值得注意的细节：顶点是在“入队时”而不是“出队时”被标记进 visited 的。这样做的效果是同一个顶点至多入队一次，队列长度不会因重复入队而膨胀；如果等到出队时再判重，同一顶点可能被多个邻居重复压入队列，虽然结果仍然正确，但会浪费额外的入队/出队开销。

多语言实现的差异

仓库为 BFS 提供了十余种语言实现，各语言的核心逻辑一致，但在“队列”与“哈希集合”的落地方式上各有取舍：

• Java（graph_bfs.java）：使用 HashSet<Vertex> 作访问集合，LinkedList 实现 Queue，offer/poll 对应入队/出队；
• JavaScript（graph_bfs.js）：直接用数组 que 模拟队列，shift() 出队、push() 入队，配合 Set 判重；
• Go（graph_bfs.go）：用切片模拟队列，出队采用 queue = queue[1:] 的切片头偏移技巧；访问集合用空结构体 map[Vertex]struct{} 表示（map 中仅存 key，正是“哈希集合”语义）；
• C（graph_dfs.c 中的 isVisited 函数，BFS 版同理）：C 语言没有内建哈希集合，参考实现退化为对结果数组 res 做线性查找，单次判重耗时 $O(|V|)$。这说明 visited 哈希集合在 C 版中是用更朴素的方式替代的，判重开销会相应上升。

遍历序列是否唯一？

不唯一。 广度优先遍历只要求按“由近及远”的顺序遍历，而多个相同距离的顶点的遍历顺序允许被任意打乱。以上述示例图为例，顶点 $1$、$3$ 的访问顺序可以交换，顶点 $2$、$4$、$6$ 的访问顺序也可以任意交换——它们都是合法的 BFS 序列。

复杂度分析

• 时间复杂度：所有顶点都会入队并出队一次，使用 $O(|V|)$ 时间；在遍历邻接顶点的过程中，由于是无向图，所有边都会被访问 $2$ 次，使用 $O(2|E|)$ 时间；总体 $O(|V| + |E|)$。
• 空间复杂度：列表 res、哈希集合 visited、队列 que 中的顶点数量最多为 $|V|$，使用 $O(|V|)$ 空间。

深度优先遍历（DFS）

核心思想：走到尽头再回头

深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。 从左上角顶点出发，访问当前顶点的某个邻接顶点，直到走到尽头时返回，再继续走到尽头并返回，以此类推，直至所有顶点遍历完成。

这种“走到尽头再返回”的算法范式通常基于递归实现。与 BFS 类似，DFS 也需要借助哈希集合 visited 记录已被访问的顶点，以避免重复访问。

递归参考实现

下面是仓库中 graph_dfs.py 的核心代码：

def dfs(graph: GraphAdjList, visited: set[Vertex], res: list[Vertex], vet: Vertex):
    """深度优先遍历辅助函数"""
    res.append(vet)              # 记录访问顶点
    visited.add(vet)            # 标记该顶点已被访问
    # 遍历该顶点的所有邻接顶点
    for adjVet in graph.adj_list[vet]:
        if adjVet in visited:
            continue           # 跳过已被访问的顶点
        dfs(graph, visited, res, adjVet)  # 递归访问邻接顶点

def graph_dfs(graph: GraphAdjList, start_vet: Vertex) -> list[Vertex]:
    """深度优先遍历"""
    res = []                   # 顶点遍历序列
    visited = set[Vertex]()     # 哈希集合，记录已被访问的顶点
    dfs(graph, visited, res, start_vet)
    return res

对比 BFS 与 DFS 两份代码，可以看到两者的结构差异正来自驱动方式的不同：

关注点	BFS	DFS
待处理顶点容器	显式队列 que	隐式递归调用栈
扩展顶点的时机	循环中“出队即扩展”	递归中“入栈即扩展”
visited 标记时机	入队时标记	进入递归（记录访问）时标记
公共部分	都遍历 graph.adj_list[vet] 邻接表并跳过已访问顶点

仓库中的图示用虚线刻画了递归过程：直虚线代表向下递推，表示开启了一个新的递归方法来访问新顶点；曲虚线代表向上回溯，表示此递归方法已经返回，回溯到了开启此方法的位置。建议将动画图与代码结合起来，在脑中模拟（或者用笔画下来）整个 DFS 过程，包括每个递归方法何时开启、何时返回。

遍历序列是否唯一？

与广度优先遍历类似，深度优先遍历序列的顺序也不是唯一的。给定某顶点，先往哪个方向探索都可以，即邻接顶点的顺序可以任意打乱，都是深度优先遍历。

以树的遍历为例，“根 → 左 → 右”“左 → 根 → 右”“左 → 右 → 根”分别对应前序、中序、后序遍历，它们展示了三种遍历优先级，然而这三者都属于深度优先遍历。

复杂度分析

• 时间复杂度：所有顶点都会被访问 $1$ 次，使用 $O(|V|)$ 时间；所有边都会被访问 $2$ 次，使用 $O(2|E|)$ 时间；总体 $O(|V| + |E|)$。
• 空间复杂度：列表 res、哈希集合 visited 的顶点数量最多为 $|V|$，递归深度最大为 $|V|$（对应一条从起点贯穿到最远的路径），因此使用 $O(|V|)$ 空间。

运行验证：驱动代码与测试

仓库中每个参考文件末尾都带有可直接运行的 Driver Code，便于对照输出验证理解。以 graph_dfs.py 为例，示例图由 $7$ 个顶点 $0 \sim 6$ 和 $6$ 条边构成：

v = vals_to_vets([0, 1, 2, 3, 4, 5, 6])
edges = [
    [v[0], v[1]], [v[0], v[3]], [v[1], v[2]],
    [v[2], v[5]], [v[4], v[5]], [v[5], v[6]],
]
graph = GraphAdjList(edges)
res = graph_dfs(graph, v[0])   # 从顶点 0 出发的深度优先遍历

按邻接表插入顺序模拟递归展开，可以得到顶点序列 0, 1, 2, 5, 4, 6, 3：从 $0$ 出发沿 $0\to 1\to 2\to 5$ 一直走到底，在 $5$ 处先后扩展 $4$（走到底回溯）和 $6$，最后回到 $0$ 再访问 $3$。BFS 的 Driver Code（graph_bfs.py）则使用 $10$ 个顶点、$12$ 条边更稠密的图，输出顶点序列 0, 1, 3, 2, 4, 6, 5, 7, 8（顶点 $9$ 未参与任何边，从源码结构看，GraphAdjList 构造时仅注册出现在边中的顶点，因此不会被遍历到）。

此外，Go 版还附带了单元测试：graph_dfs_test.go 与 graph_bfs_test.go 构造与 Python 版相同的示例图并调用遍历函数，可以在 CI 中持续验证多语言实现的行为一致性。

小结

• BFS 与 DFS 是图论中两类互补的遍历范式：BFS 用队列驱动、逐层向外扩展，天然适合求“最短路（最少边数）”类问题；DFS 用递归栈驱动、深入到底再回溯，天然适合路径枚举、连通性判定等问题。
• 两者都以邻接表为载体获取邻接顶点，以 visited 哈希集合保证每个顶点只被访问一次，时间复杂度均为 $O(|V| + |E|)$，空间复杂度均为 $O(|V|)$。
• 遍历序列在“等距/同层顶点可任意换序”的意义上不唯一，因此比较两份遍历结果时应关注相对层次（BFS）或前驱关系（DFS），而非逐位相等。
• 仓库中 codes/python、codes/java、codes/go、codes/javascript、codes/c 等目录提供了同一算法的对照实现，适合作为学习遍历算法时逐语言精读的入口。