5.1 图的表示、DFS 与 BFS

学习图时必须分清两件事：哪些关系存在，以及计算机怎样存储这些关系。 深度优先搜索（DFS）和广度优先搜索（BFS）可以作用于同一个抽象图，但二者的 前沿管理规则不同，因此探索顺序也不同。严谨的执行轨迹必须说明表示方式、 检查邻接点的顺序，以及顶点在什么时候算作已发现。

动机

道路、通信连接、先修关系和程序状态都可以用图表示。图不像数组那样有唯一的 “下一个”元素；一个顶点可以有零条、一条或多条离开它的边。因此，遍历既要 用一个前沿保存待处理顶点，也要记录哪些顶点已经被发现。

• DFS 沿一条尚未完成的路径尽量深入，适合用递归或栈实现。
• BFS 先处理最早发现的顶点，用队列按距离层次向外扩展。

如果目的只是访问顶点，二者都不需要使用边权。但当每条边的成本相同时，BFS 还能计算从起点到每个可达顶点的最少边数。

定义

按照课程用语，**路径（path）**是相邻两项之间都有边的顶点序列，可以重复 顶点；简单路径才不重复顶点。无权路径的长度是边数，而不是顶点数。 **环（cycle）**从同一顶点开始和结束；简单环除首尾外不重复顶点。没有环的 图称为无环图。

如果存在从 u 到 v 的有向路径，就称 v 从 u 可达。有向图中的 可达性不一定对称。在无向图中，两个顶点之间存在路径便是连通；每一对顶点都 连通的图称为连通图，而极大的连通部分称为连通分量。有向顶点的出度统计离开 它的边，入度统计进入它的边。

选择表示方式

设顶点编号为 0,1,...,|V|-1。

表示方式会直接改变取得邻接点的成本：

稠密图或大量直接边查询可能适合使用矩阵；邻接表不必扫描不存在的边，因此更 适合下文的线性时间遍历。在无向邻接表中，每条边会在两个列表里各出现一次； 这只增加常数因子，不改变渐近上界。

深度优先搜索

DFS 发现一个顶点后，选择第一个未发现的邻接点，暂停当前工作，再深入该邻接 点。递归调用保存被暂停的工作；当一个顶点没有未发现的邻接点时，调用结束并 回溯。

DFS-VISIT(u):
    discovered[u] = true
    process u
    for each v in Adj[u], in the stated order:
        if not discovered[v]:
            parent[v] = u
            DFS-VISIT(v)

DFS-FOREST(G):
    将所有顶点设为未发现，并将所有 parent 设为 null
    按给定顺序逐个考察顶点 u:
        if not discovered[u]:
            DFS-VISIT(u)

单次 DFS-VISIT(s) 恰好探索从 s 可达的顶点；DFS-FOREST 的外层循环则 覆盖非连通图，每个新根开始另一棵 DFS 树。显式栈可以代替递归，但若想得到 相同轨迹，就必须留意入栈顺序：一次把多个邻接点压入后进先出的栈，可能使其 处理顺序反转。

父边组成一棵 DFS 树；使用外层循环时则组成 DFS 森林。它记录每个顶点最初 怎样被发现，并不表示原图的其他边消失了。

广度优先搜索与前沿不变量

BFS 使用先进先出的队列。队列中保存已经发现、但出边邻接表尚未完全处理的 顶点。安全的发现规则是：

顶点在入队时立即标记为已发现，不能等到以后出队才标记。

BFS(G, s):
    for each vertex v:
        discovered[v] = false
        distance[v] = infinity
        parent[v] = null
    discovered[s] = true
    distance[s] = 0
    enqueue(Q, s)

    while Q is not empty:
        u = dequeue(Q)
        process u
        for each v in Adj[u], in the stated order:
            if not discovered[v]:
                discovered[v] = true
                distance[v] = distance[u] + 1
                parent[v] = u
                enqueue(Q, v)

discovered[v] 的赋值发生在入队之前。如果另一个前沿顶点也有边通往 v， 它会看到 v 已被认领，不能把它重复加入队列。“已发现”不等于“已处理完”： 队列中的顶点虽然还没有出队，却已经是已发现状态。

单次 BFS 也只处理从源点可达的部分。要遍历无向图的每个连通分量，就从仍未 发现的顶点重新开始 BFS，直到没有剩余顶点。

定理 / 命题

这个结论要求每条边成本相同。如果权重不同，边数较少的路径可能有更大的总 权重；普通 BFS 仍然最小化边数，却不一定最小化加权成本。

单源搜索可以用实际到达的顶点和实际扫描的出边写出更紧的上界；通常采用的 全图上界对应遍历所有连通部分的版本。

证明思路

先证明 BFS 的最短路径性质。开始时只有 s 的距离为 0。在处理 u 时首次 发现 v，算法设置 distance[v]=distance[u]+1。由于队列先进先出，距离 k 的顶点一定在新发现的距离 k+1 顶点之前被处理。假如 v 有更短路径， 该路径应当从更早的层到达并更早发现 v，产生矛盾。因此第一次赋予的距离 最小；每沿一个 parent 指针，距离恰好减一，所以 parent 链重建最短路径。

再证明时间上界。初始化和外层循环为 O(|V|)。每个顶点只会第一次发现一次， 所以只进入递归/栈或队列一次。所有邻接表合起来，对每条有向边扫描一次；对 无向边扫描两次，因此总时间为 O(|V|+|E|)。若使用矩阵，每处理一个顶点都 要扫描 |V| 个表项，全图遍历便是 Theta(|V|^2)。

例题

考虑课程中的 A,B,C,D,E,F 有向图，固定邻接表顺序如下：

A: B, D
B: C, D
C: F, D, E
D: E
E: —
F: —

    A B C D E F
A   0 1 0 1 0 0
B   0 0 1 1 0 0
C   0 0 0 1 1 1
D   0 0 0 0 1 0
E   0 0 0 0 0 0
F   0 0 0 0 0 0

常见错误

• 单源搜索不会自动访问不可达顶点；完整遍历需要外层循环。
• 有向邻接矩阵不一定对称，有向可达性也不一定双向成立。
• BFS 保证最少边数，不保证任意加权成本最小。
• 一边扫描邻接矩阵的整行，一边声称 O(|V|+|E|)，是混合了两种表示法。
• DFS/BFS 的父树只包含发现边，不包含原图中的所有边。

总结

• 图可以是有向或无向、加权或无权。
• 路径、环、可达性和连通性描述抽象图，与存储方式相互独立。
• 矩阵查询一条边快，但空间和整行扫描都是平方量级；列表只存实际邻接点。
• DFS 用递归或栈先深入，再回溯。
• BFS 用队列按照非递减的边距离层次扩展。
• 稳健的 BFS 在入队时标记，保证每个顶点最多入队一次。
• BFS 的 parent 和 distance 数组给出无权最短路径。
• 邻接表 DFS/BFS 的全图运行时间是 O(|V|+|E|)。

练习

1. 对 A–F 图，写出 C 的出边邻接点和邻接矩阵对应行，并解释为什么 列表成本取决于出度，而矩阵整行扫描不取决于出度。
2. 先从 D 做递归 DFS，再从 D 做 BFS。按照固定列表顺序写出两个发现 顺序，并指出哪些顶点不可达。
3. 原来从 A 出发的 BFS 中，C 也有边到 E，为什么 E 仍由 D 得到 距离 2？重建所存储的 parent 路径。
4. 如果 visited 标记延迟到出队，写出最早含有重复项的队列状态，并指出由哪 两条边造成。
5. 一个图有 10,000 个顶点和 20,000 条有向边。比较全图矩阵遍历概念上 扫描的位置数与邻接表的渐近工作量。

解答