图的遍历¶
树代表的是“一对多”的关系,而图则具有更高的自由度,可以表示任意的“多对多”关系。因此,我们可以把树看作图的一种特例。显然,树的遍历操作也是图的遍历操作的一种特例。
图和树都需要应用搜索算法来实现遍历操作。从一个点出发,可以先看一步能到的点,再看两步能到的点,这叫广度优先遍历(BFS)。也可以沿一条新路尽量走远,走不下去了就退回上一个岔口换方向,这叫深度优先遍历(DFS)。
一张图,先手动走两遍¶
把字母看成房间,连线表示双向可通行,跨一条线算一步。从 A 出发,遇到多个未发现的邻居时按字母顺序考虑。
**广度优先(BFS)**像维护一张待办列表:先放 A,每次拿出队首,把新发现的邻居依次排到末尾。节点一入队就标记为已发现,否则沿着环会反复发现同一个节点。
| 本轮拿出 | 本轮新入队 | 处理后的队列 |
|---|---|---|
| A | B、C | B、C |
| B | D | C、D |
| C | E | D、E |
| D | 无,E 已入队 | E |
| E | 无 | 空 |
从 A 出发,B、C 距离 1 步,D、E 距离 2 步。处理第 1 层时发现的第 2 层排在队尾,所以不会抢在第 1 层之前。
**深度优先(DFS)**先走一条路,走不动再回头。沿着 A → B → D → E → C 走,到 C 时它的邻居 A、E 都已经到过,便逐层返回。DFS 能到达同样的房间,但第一次走到 C 时已经走了 4 条边,尽管 A 与 C 本来相邻。因此要找每条边代价都相同的图上的最少步数,选 BFS;若要逐条探索分支,走不通就退回来换一条(回溯),或者检查是否能沿箭头绕回原点,DFS 常更自然。
先预测:只删掉 A–C 这条边,会发生什么?
新图只剩 A—B—D—E—C 这条路。BFS 和 DFS 都按 A、B、D、E、C 发现节点。从 A 到 C 的最少步数变为 4。两种算法给出相同访问顺序,源于图上没有分支可选。
可以把同样的图放进 VisuAlgo,先预测每一步再看动画。后面的代码展示如何把纸面上的队列、递归和标记变成程序。
广度优先遍历¶
广度优先遍历是一种由近及远的遍历方式,从某个节点出发,始终优先访问距离最近的顶点,并一层层向外扩张。如下图所示,从左上角顶点出发,先遍历它的邻接顶点,再遍历这些顶点新发现的邻居,直至能从起点到达的顶点都访问完毕。
算法实现¶
BFS 通常借助队列来实现,代码如下所示。队列具有“先入先出”的性质,这与 BFS 的“由近及远”的思想异曲同工。
- 将遍历起始顶点
startVet加入队列,并开启循环。 - 在循环的每轮迭代中,弹出队首顶点并记录访问。只将尚未发现的邻接顶点加入队尾,入队时立即标记。
- 队列空时结束。若图不连通,要从其余未访问的顶点另外开始遍历。
为了防止重复遍历顶点,我们需要借助一个哈希集合 visited 来记录哪些节点已被访问。
Tip
哈希集合可以看作一个只存储键的哈希表。正常散列和负载假设下,平均可用 \(O(1)\) 时间记录或检查一个键。这里用它判断一个节点是否已进入待处理队列。
def graph_bfs(graph: GraphAdjList, start_vet: Vertex) -> list[Vertex]:
"""广度优先遍历"""
# 使用邻接表来表示图,以便获取指定顶点的所有邻接顶点
# 顶点遍历序列
res = []
# 哈希集合,用于记录已被访问过的顶点
visited = set[Vertex]([start_vet])
# 队列用于实现 BFS
que = deque[Vertex]([start_vet])
# 以顶点 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
代码相对抽象,建议对照下图来加深理解。
广度优先遍历的序列是否唯一?
不唯一。广度优先遍历只要求按“由近及远”的顺序遍历,而多个相同距离的顶点的遍历顺序允许被任意打乱。以上图为例,顶点 \(1\)、\(3\) 的访问顺序可以交换,顶点 \(2\)、\(4\)、\(6\) 的访问顺序也可以任意交换。
复杂度分析¶
时间复杂度:所有顶点都会入队并出队一次,使用 \(O(|V|)\) 时间;在遍历邻接顶点的过程中,由于是无向图,因此所有边都会被访问 \(2\) 次,使用 \(O(2|E|)\) 时间;总体使用 \(O(|V| + |E|)\) 时间。
空间复杂度:列表 res ,哈希集合 visited ,队列 que 中的顶点数量最多为 \(|V|\) ,使用 \(O(|V|)\) 空间。
深度优先遍历¶
深度优先遍历是一种优先走到底、无路可走再回头的遍历方式。如下图所示,从左上角顶点出发,访问当前顶点的某个邻接顶点,直到走到尽头时返回,再继续走到尽头并返回,以此类推,直至所有顶点遍历完成。
算法实现¶
这种“走到尽头再返回”的算法范式通常基于递归来实现。与广度优先遍历类似,在深度优先遍历中,我们也需要借助一个哈希集合 visited 来记录已被访问的顶点,以避免重复访问顶点。
深度优先遍历的算法流程如下图所示。
- 直虚线代表向下递推,表示开启了一个新的递归方法来访问新顶点。
- 曲虚线代表向上回溯,表示此递归方法已经返回,回溯到了开启此方法的位置。
为了加深理解,建议将下图与代码结合起来,在脑中模拟(或者用笔画下来)整个 DFS 过程,包括每个递归方法何时开启、何时返回。
深度优先遍历的序列是否唯一?
与广度优先遍历类似,深度优先遍历序列的顺序也不是唯一的。给定某顶点,先往哪个方向探索都可以,即邻接顶点的顺序可以任意打乱,都是深度优先遍历。
以树的遍历为例,“根 \(\rightarrow\) 左 \(\rightarrow\) 右”“左 \(\rightarrow\) 根 \(\rightarrow\) 右”“左 \(\rightarrow\) 右 \(\rightarrow\) 根”分别对应前序、中序、后序遍历,它们展示了三种遍历优先级,然而这三者都属于深度优先遍历。
复杂度分析¶
时间复杂度:所有顶点都会被访问 \(1\) 次,使用 \(O(|V|)\) 时间;所有边都会被访问 \(2\) 次,使用 \(O(2|E|)\) 时间;总体使用 \(O(|V| + |E|)\) 时间。
空间复杂度:列表 res ,哈希集合 visited 顶点数量最多为 \(|V|\) ,递归深度最大为 \(|V|\) ,因此使用 \(O(|V|)\) 空间。
下一步:给边加上代价或顺序¶
BFS 的层数等于最少经过的边数。若每条边代价不同,接着读最短路径。如果边表示「必须先完成」,则需要检查当前前置任务是否都已结束,接着读拓扑排序。























