CS61B 课程笔记（DISC 12 Graphs, Sorting)

1 热身：最小生成树（MST）和最短路径（SP）

我们假设一个可能的加权无向图来解释算法的执行过程。假设顶点和边如下：

顶点：$ A, B, C, D, E, F, G, H$
边（带权重）：
- $ A B$ 权重 1
- $A \leftrightarrow C$ 权重 4
- $ B C$ 权重 2
- $B \leftrightarrow D$ 权重 5
- $C \leftrightarrow D$ 权重 1
- $D F $ 权重 3
- $F H $ 权重 1
- $F \leftrightarrow G$ 权重 2
- $H \leftrightarrow E$ 权重 5

Dijkstra 算法步骤：

初始化：
- 起点设为 $A$ ，距离 $A$ 自己为 0，其他所有顶点初始距离为 $ $ 。
- 优先队列初始化为 $ [(A, 0)] $。
访问顶点 A：
- 从优先队列中弹出 $ A$ ，它是距离最近的顶点（距离 0）。
- 更新邻居 $B$ 和 $C $ 的距离：
  - $dist(B) = 1$ （通过边 $ A B$ ）
  - $dist(C) = 4$ （通过边 $A C $）
- 将 B 和 C 加入优先队列： $[(B, 1), (C, 4)] $。
访问顶点 B：
- 从优先队列中弹出 $B $（距离 1）。
- 更新邻居 $C$ 和 $D$ 的距离：
  - $dist(C) = \min(4, 1 + 2) = 3$ （通过边 $ B C $）
  - $dist(D) = 1 + 5 = 6 $ （通过边 $B \leftrightarrow D$ ）
- 将 $C $ 和 $D$ 加入优先队列：$ [(C, 3), (C, 4), (D, 6)]$ 。
- 因为 $C$ 的距离已经被更新为 3，忽略优先队列中的 $(C, 4)$ 。
访问顶点 C：
- 从优先队列中弹出 $C $（距离 3）。
- 更新邻居 $ D$ 的距离：
  - $ dist(D) = (6, 3 + 1) = 4$ （通过边 $C \leftrightarrow D$ ）
- 更新后优先队列为 $ [(D, 4), (D, 6)]$ 。
访问顶点 D：
- 从优先队列中弹出 $D$ （距离 4）。
- 更新邻居 $F$ 的距离：
  - $dist(F) = 4 + 3 = 7 $ （通过边 $ D F$ ）
- 将 $ F $ 加入优先队列： $[(F, 7)]$ 。
访问顶点 F：
- 从优先队列中弹出 $F$ （距离 7）。
- 更新邻居 $H$ 和 $ G$ 的距离：
  - $dist(H) = 7 + 1 = 8$ （通过边 $ F H $）
  - $dist(G) = 7 + 2 = 9$ （通过边 $ F G$ ）
- 将 $H$ 和 $G $ 加入优先队列： $[(H, 8), (G, 9)] $。
访问顶点 H：
- 从优先队列中弹出 $H$ （距离 8）。
- 更新邻居 $ E $ 的距离：
  - $dist(E) = 8 + 5 = 13$ （通过边 $H E $）
- 将 $ E$ 加入优先队列： $[(G, 9), (E, 13)]$ 。
访问顶点 G：
- 从优先队列中弹出 $ G $（距离 9）。没有其他需要更新的顶点。
访问顶点 E：
- 从优先队列中弹出 $ E$ （距离 13）。没有其他需要更新的顶点。

最终访问顺序：

$A → B → C → D → F → H → G → E$

2 最短路径与最小生成树

2 概念性 MST 和 SP

请回答以下关于加权无向图的最小生成树（MST）和最短路径（SP）算法的问题。如果问题是 True/False 且语句为真，请提供解释。如果语句为假，请提供反例。

(a) (T/F) 如果所有边的权重都相等且为正，从节点 A 开始的广度优先搜索（BFS）将返回从节点 A 到目标节点 B 的最短路径。

答：真。

解释：广度优先搜索（BFS）适用于无权图或所有边的权重相等的图。在这种情况下，BFS 通过层次遍历的方式寻找最短路径。每一步访问的邻居节点距离增加相同的权重，因此路径上的跳数即为最短路径。当所有边的权重相等时，BFS 能保证找到最短路径。

(b) (T/F) 如果所有边的权重都不同，则任意两个顶点之间的最短路径是唯一的。

答：假。

反例：考虑如下图形：
1
2
3
4
5
a
/ \
b c
\ /
d
- 边权重： ab = 1 , ac = 2 , bd = 2 , cd = 1 。
- 从 a 到 d 的最短路径有两条可能的选择：
  - $ a b d $，总权重为 3。
  - $ a c d$ ，总权重也是 3。
这个反例显示即使所有边权重不同，任意两个顶点之间的最短路径也不一定是唯一的。

(c) (T/F) 在所有边的权重上添加一个正整数 k 将不会影响任意顶点之间的最短路径。

答：假。

解释：向所有边的权重上添加一个正整数 k 会改变最短路径的优先选择。较少边数的路径在总权重增加后可能会变得相对更优。考虑以下示例：
1
2
a -- b -- c
1 1 1
- 从 a 到 c 的最短路径是 $ a b c$ ，权重为 2。
- 现在假设我们向每条边添加 10，则每条边的权重变为 11。此时，从 a 到 c 的直接路径（权重 11）比原先的最短路径（权重 22）要短。

(d) 画一个加权图（可以是有向或无向），其中 Dijkstra 算法将错误地给出从某个顶点的最短路径。

反例：Dijkstra 算法在有负权边的情况下无法保证正确性。
1
2
3
4
5
a --(1)-- b --(1)-- c
\ |
(4) (-3)
\ /
-------d
- 从 a 到 c 的最短路径应该是 $a \to d \to b \to c$ ，总权重为 2。
- 但如果使用 Dijkstra 算法，它在 $ a b c $ 处会停下，总权重为 2，这是错误的结果。因为 Dijkstra 算法一旦访问一个顶点就无法再次访问它，导致负权边被忽略。

(e) (T/F) 在所有边的权重上添加一个正整数 k 将不会影响图的任何最小生成树。

答：真。

解释：对于最小生成树（MST），只关注的是相对边权重，而不是边的绝对值。如果我们在所有边上添加同样的常数 k ，最小生成树的结构不会改变。因为即使增加了权重，每一对顶点之间跨切割的最小边仍然是相同的，所以最小生成树不受影响。

(f) (T/F) 普里姆算法在图中存在负权边时仍然有效。

答：真。

解释：普里姆算法和克鲁斯克尔算法一样，依赖于最小生成树的切割性质。它只在意相对的边权值，因此负权边不会影响其构建最小生成树的过程。无论边的权重是否为负，只要使用切割定理找到最小边，普里姆算法依然能够正确地构建最小生成树。

(g) 为什么在克鲁斯克尔算法中使用不相交集（Disjoint Sets）？

答：不相交集（Disjoint Set Union, DSU）用于帮助检测克鲁斯克尔算法中潜在的环。当我们向生成树中添加一条边时，需要确定该边是否会导致一个环。如果它的两个顶点属于同一个连通分量，添加该边会形成一个环。因此，不相交集可以高效地检查两个顶点是否属于同一连通分量并且能快速合并不同的连通分量。

(h) (T/F) 普里姆算法最后添加到最小生成树的边总是最小生成树的最高权重边。

答：假。

反例：考虑如下图形，并从顶点 s 开始执行普里姆算法：
1
2
s -- a -- t
(2) (3) (1)
- 从 s 开始，普里姆算法会首先选择 $s \to a$ ，权重 2，然后选择 $a t $，权重 1。这里最后添加的边并不是权重最大的边（最大权重为 3 的边 $s a $ 反而是最早添加的）。