CS61B 课程笔记（Lecture 28 Graph Traversals)

图遍历概述

• 深度优先搜索（DFS）: 从起始节点开始，沿着一条路径深入，直到无法继续为止，然后回溯。
• 广度优先搜索（BFS）: 从起始节点开始，先访问所有直接相连的节点，然后逐层向外扩展，访问下层节点。

广度优先搜索（BFS）

BFS按照层级访问图的节点，具体步骤如下：

伪代码

1. 初始化一个空队列（fringe）
2. 将起始顶点添加到队列中
3. 标记起始顶点
4. 当队列不为空：
5.    从队列中移除顶点 v
6.    对于顶点 v 的每个邻居 n：
7.        如果 n 未被标记：
8.            将 n 添加到队列
9.            标记 n
10.           edgeTo[n] = v
11.           distTo[n] = distTo[v] + 1

• fringe: 存储待访问节点的队列。
• edgeTo: 记录如何到达每个节点。
• distTo: 记录从起始顶点到每个节点的距离（假设每条边的距离为 1）。

BFS的特点

• 在BFS中，节点一被添加到队列就立即标记。
• BFS适用于求解最短路径问题。

深度优先搜索（DFS）

DFS的实现有递归和迭代两种方式：

伪代码（迭代）

1. 初始化一个空栈（fringe）
2. 将起始顶点推入栈中
3. 当栈不为空：
4.    从栈中弹出一个顶点
5.    如果该顶点未被标记：
6.        标记该顶点
7.        访问该顶点
8.        对于该顶点的每个邻居：
9.            如果邻居未被标记：
10.               将邻居推入栈中

图的表示方法

1. 邻接列表（Adjacency List）:

   • 使用一个数组，数组的每个位置代表一个顶点，位置中存储该顶点的所有邻居。
   • 是实践中最常用的表示方法。

   示例：

   int[][] adjList = {
       {1, 2},    // 节点 0 的邻居
       {0, 3},    // 节点 1 的邻居
       {0},       // 节点 2 的邻居
       {1}        // 节点 3 的邻居
   };

2. 邻接矩阵（Adjacency Matrix）:

   • 使用一个二维数组，大小为 (\(N \times N\))，$N \(为顶点数，数组的 (\)i, j$) 项为 true 表示有从 $i \(到\)j$ 的边，否则为 false。

   示例：

   |   | 0 | 1 | 2 | 3 |
   |---|---|---|---|---|
   | 0 | 0 | 1 | 1 | 0 |
   | 1 | 1 | 0 | 0 | 1 |
   | 2 | 1 | 0 | 0 | 0 |
   | 3 | 0 | 1 | 0 | 0 |

3. 边集合（Edge Collection）:

   • 使用 HashSet 存储边，每条边由一对整数表示。

效率分析

• 邻接列表的遍历: (\(O(V + E)\))，其中 (\(V\)) 是顶点数，(\(E\)) 是边数。
• 邻接矩阵的遍历: (\(O(V^2)\))，因为每次都要检查每一对顶点是否相邻。

操作	邻接列表	邻接矩阵
查询边 (u, v)	\(O(E)\)	\(O(1)\)
获取邻居	\(O(E)\)	\(O(V)\)
计算顶点数量	\(O(1)\)	\(O(1)\)
计算边数量	\(O(1)\)	\(O(1)\)

总结

• DFS和BFS: 这两种遍历方法可以用于图的各种算法，选择合适的遍历方法对解决问题至关重要。
• 图的实现: 选择合适的数据结构会影响程序的运行效率和内存使用情况。