图的遍历

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

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

广度优先遍历(BFS)

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

图 9-9   图的广度优先遍历

1.   算法实现

BFS 通常借助队列来实现，代码如下所示。队列具有“先入先出”的性质，这与 BFS 的“由近及远”的思想异曲同工。

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

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

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

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRubyZig

/* 广度优先遍历 */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
List<Vertex> graphBFS(GraphAdjList graph, Vertex startVet) {
    // 顶点遍历序列
    List<Vertex> res = new ArrayList<>();
    // 哈希集合，用于记录已被访问过的顶点
    Set<Vertex> visited = new HashSet<>();
    visited.add(startVet);
    // 队列用于实现 BFS
    Queue<Vertex> que = new LinkedList<>();
    que.offer(startVet);
    // 以顶点 vet 为起点，循环直至访问完所有顶点
    while (!que.isEmpty()) {
        Vertex vet = que.poll(); // 队首顶点出队
        res.add(vet);            // 记录访问顶点
        // 遍历该顶点的所有邻接顶点
        for (Vertex adjVet : graph.adjList.get(vet)) {
            if (visited.contains(adjVet))
                continue;        // 跳过已被访问的顶点
            que.offer(adjVet);   // 只入队未访问的顶点
            visited.add(adjVet); // 标记该顶点已被访问
        }
    }
    // 返回顶点遍历序列
    return res;
}

代码相对抽象，建议对照图 9-10 来加深理解。

<1><2><3><4><5><6><7><8><9><10><11>

图 9-10   图的广度优先遍历步骤

>[!QUESTION] 广度优先遍历的序列是否唯一? 不唯一。广度优先遍历只要求按“由近及远”的顺序遍历，而多个相同距离的顶点的遍历顺序允许被任意打乱。以图 9-10 为例，顶点 1、3 的访问顺序可以交换，顶点 2、4、6 的访问顺序也可以任意交换。

2.   复杂度分析

时间复杂度：所有顶点都会入队并出队一次，使用 O(|V|) 时间；在遍历邻接顶点的过程中，由于是无向图，因此所有边都会被访问 2 次，使用 O(2|E|) 时间；总体使用 O(|V|+|E|) 时间。

空间复杂度：列表 res ，哈希集合 visited ，队列 que 中的顶点数量最多为 |V| ，使用 O(|V|) 空间。

深度优先遍历(DFS)

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

图 9-11   图的深度优先遍历

1.   算法实现

这种“走到尽头再返回”的算法范式通常基于递归来实现。与广度优先遍历类似，在深度优先遍历中，我们也需要借助一个哈希集合 visited 来记录已被访问的顶点，以避免重复访问顶点。

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRubyZig

/* 深度优先遍历辅助函数 */
void dfs(GraphAdjList graph, Set<Vertex> visited, List<Vertex> res, Vertex vet) {
    res.add(vet);     // 记录访问顶点
    visited.add(vet); // 标记该顶点已被访问
    // 遍历该顶点的所有邻接顶点
    for (Vertex adjVet : graph.adjList.get(vet)) {
        if (visited.contains(adjVet))
            continue; // 跳过已被访问的顶点
        // 递归访问邻接顶点
        dfs(graph, visited, res, adjVet);
    }
}

/* 深度优先遍历 */
// 使用邻接表来表示图，以便获取指定顶点的所有邻接顶点
List<Vertex> graphDFS(GraphAdjList graph, Vertex startVet) {
    // 顶点遍历序列
    List<Vertex> res = new ArrayList<>();
    // 哈希集合，用于记录已被访问过的顶点
    Set<Vertex> visited = new HashSet<>();
    dfs(graph, visited, res, startVet);
    return res;
}

深度优先遍历的算法流程如图 9-12 所示。

• 直虚线代表向下递推，表示开启了一个新的递归方法来访问新顶点。
• 曲虚线代表向上回溯，表示此递归方法已经返回，回溯到了开启此方法的位置。

为了加深理解，建议将图 9-12 与代码结合起来，在脑中模拟（或者用笔画下来）整个 DFS 过程，包括每个递归方法何时开启、何时返回。

<1><2><3><4><5><6><7><8><9><10><11>

图 9-12   图的深度优先遍历步骤

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

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

2.   复杂度分析

时间复杂度：所有顶点都会被访问 1 次，使用 O(|V|) 时间；所有边都会被访问 2 次，使用 O(2|E|) 时间；总体使用 O(|V|+|E|) 时间。

空间复杂度：列表 res ，哈希集合 visited 顶点数量最多为 |V| ，递归深度最大为 |V| ，因此使用 O(|V|) 空间。

遍历方式选择

图的遍历方法主要包括 深度优先搜索（DFS） 和 广度优先搜索（BFS），根据不同的应用场景选择合适的遍历方法非常重要。以下是两种遍历方法的特点和常见的使用场景：

---

1. 深度优先搜索（DFS）

特点

• 使用递归（或栈）实现，从起始顶点开始深入到某一分支的尽头后，再回溯到上一级继续探索其他分支。
• 更注重“路径探索”，会优先走一条路径直到走不通为止。

复杂度

• 时间复杂度：O(V+E)，其中 V 是顶点数，E 是边数。
• 空间复杂度：在递归实现中，取决于递归深度，最坏情况下为 O(V)。

适用场景

1. 路径问题：

   • 查找是否存在从某个顶点到另一个顶点的路径。
   • 找到图中的所有路径。
   • 解决迷宫问题（例如从起点到终点的路径搜索）。

2. 连通性问题：

   • 判断图是否是连通的（无向图）。
   • 统计无向图中的连通分量。

3. 拓扑排序：

   • 在有向无环图（DAG）中，通过 DFS 可以进行拓扑排序。

4. 强连通分量：

   • 使用 Tarjan 算法或 Kosaraju 算法（基于 DFS）查找图中的强连通分量。

5. 环检测：

   • 检查有向图或无向图中是否存在环。

优点

• 实现简单（递归版本代码较为简洁）。
• 能够快速探索一条路径，适合解决递归式问题。

缺点

• 深度过大时可能会导致栈溢出。
• 在稠密图中，DFS 可能会重复遍历大量顶点（需要辅助标记数组来避免）。

---

2. 广度优先搜索（BFS）

特点

• 使用队列实现，从起始顶点开始按层级逐层向外扩展，直至遍历所有顶点或找到目标。
• 更注重“层级扩展”，优先探索距离起点最近的顶点。

复杂度

• 时间复杂度：O(V+E)，其中 V 是顶点数，E 是边数。
• 空间复杂度：需要队列存储顶点，最坏情况下为 O(V)。

适用场景

1. 最短路径问题：

   • 无权图中，BFS 可以找到从起点到终点的最短路径。
   • 广泛应用于迷宫、棋盘游戏等场景。

2. 分层遍历：

   • 按照层级依次遍历所有顶点。
   • 解决问题时有明确的分层顺序，例如社交网络中的好友推荐。

3. 双向搜索：

   • BFS 的基础上可以扩展为双向 BFS，从起点和目标点同时开始搜索，效率更高。

4. 连通性检测：

   • 判断无向图是否连通。

优点

• 能够找到最短路径（无权图）。
• 不会出现递归栈溢出问题，适合深度较大的图。

缺点

• 在稠密图中，需要较大的空间来存储队列。
• 实现相对复杂，需要手动管理队列。

---

3. DFS 和 BFS 的比较

特点	DFS	BFS
实现方式	栈（递归或手动）	队列
优先级	深度优先（先探索一条路径）	广度优先（逐层扩展）
适合场景	路径探索、递归问题、拓扑排序	最短路径、层级遍历
复杂度	时间复杂度 O(V+E)	时间复杂度 O(V+E)
空间复杂度	递归栈深度 O(V)	队列大小 O(V)O(V)
优点	实现简单，适合深度路径问题	能找到最短路径，无递归栈溢出
缺点	可能栈溢出，不适合层级问题	队列占用空间较大，可能遍历较慢

---

4. 选择遍历方法的依据

什么时候选择 DFS？

• 当问题与路径搜索、连通性检测相关时：
  • 例如：判断两个节点是否相连，寻找所有可能的路径。
• 当问题需要按深度优先顺序探索（即先解决深层问题）。
• 当问题的逻辑可以自然地用递归实现。
• 图的深度不大，或者可以确保不会栈溢出。

什么时候选择 BFS？

• 当需要找到最短路径时（无权图）。
  • 例如：棋盘游戏中寻找最短步数。
• 当问题需要按层级逐层扩展。
• 图的深度较大，使用 DFS 可能会导致栈溢出时。
• 需要解决类似网络流的层级遍历问题（如 Ford-Fulkerson）。

---

5. 示例问题及推荐遍历方法

问题类型	推荐方法	原因
判断是否存在一条路径	DFS	DFS 能够快速找到一条路径，不需要层级顺序。
找到两点间的最短路径	BFS	BFS 保证找到的是最短路径（无权图）。
检测是否是连通图	DFS / BFS	两者皆可，DFS 实现简单，BFS 空间利用更高效。
迷宫求解（路径搜索）	DFS	DFS 适合探索所有可能路径并找到目标。
迷宫求解（最短路径）	BFS	BFS 能够快速找到最短路径（层级搜索）。
查找所有连通分量	DFS	DFS 实现较为简单，适合对每个连通分量进行探索。
拓扑排序（有向无环图）	DFS	DFS 后序遍历可生成拓扑排序。
找到强连通分量（有向图）	DFS	Tarjan 或 Kosaraju 算法基于 DFS。
检测无向图中的环	DFS	DFS 可以通过回溯检测是否存在环。
检测有向图中的环	DFS	DFS 可以通过追踪递归栈上的节点检测是否存在环。

---

总结

• DFS 适合==深度探索==、==路径搜索==以及需要==递归==解决的问题。
• BFS 适合==分层级的遍历==，尤其是在无权图中寻找==最短路径==时。