需要将多个组件的针脚 连接在一起。要连接n个针脚，可以使用 n-1 根连线，每根连线连接两个针脚。很显然，希望所使用的连线长度最短

用一个连通无向图 G = (V, E) 来予以表示，这里的 V 是针脚的集合，E 是针脚之间的可能连接，并且对于每条边 (u, v) ∈ E，为其赋予权重 w(u, v) 作为连接针脚 u 和针脚 v 的代价 (也就是连线的长度)。希望找到一个无环子集 T⊆E，既能够将所有的结点 (针脚)连接起来，又具有最小的权重，即 w(T) = ∑(u,v)∈T w(u,v) 的值最小。由于 T 是无环的，并且连通所有的结点，因此，T 必然是一棵树。称这样的树为 (图G的) 生成树，因为它是由图G所生成的。称求取该生成树的问题为 最小生成树问题

解决最小生成树问题的 两种算法：Kruskal 算法 和 Prim 算法。如果使用普通的二叉堆，那么可以很容易地 将这两个算法的时间复杂度限制在 O(E lg V) 的数量级内。但如果 使用斐波那契堆，Prim 算法的运行时间将改善为 O(E + V lg V)。此运行时间在 |V| 远远小于 |E| 的情况下较二叉堆有很大改进

二叉堆 和 斐波那契堆 都是 用于实现优先队列的一种数据结构
两种最小生成树算法 都是贪心算法。贪心算法的每一步 必须在多个可能的选择中选择一种。树T中的结点 是指由 T 中的边连接的结点

一、二叉堆

1. 结构特点：
   二叉堆是一种完全二叉树，分为最大堆 和 最小堆
   最大堆：每个节点的值都大于等于其子节点的值
   最小堆：每个节点的值都小于等于其子节点的值
   二叉堆通常用数组表示，以节省空间和提高操作效率
2. 操作复杂度：
   插入元素：O(log n)
   删除堆顶元素：O(log n)
   查找最小/最大元素：O(1)
   建堆：O(n)
   建堆过程主要有两种方法：
   1）逐个插入法：将第一个元素作为堆的根节点。依次将后续元素插入堆的末尾。每插入一个元素后，执行上浮操作，使新插入的元素在堆中找到合适的位置，维持堆的性质
   时间复杂度：每次插入的时间复杂度为O(log n)，总时间复杂度为O(n log n)
   2）“自下而上”方法（Heapify）：利用堆的特性，从最后一个非叶子节点（对于完全二叉树，最后一个非叶子节点的索引为 floor(n/2) - 1，其中n为节点总数）开始，向上依次对每个节点 执行下沉操作，以调整子树满足堆性质
   时间复杂度为O(n)，适合一次性将大量元素构建成堆，因为 下沉操作的时间复杂度取决于树的高度，但与逐个插入法不同的是，数量更多的树（更底层）的需要调整的高度 相对（数量更少的 更顶层的）较低
   在实际应用中，Heapify方法通常更受欢迎，尤其是在 需要从无序数组快速构建堆的场景，如堆排序算法中
3. 使用场景：
   二叉堆适用于需要频繁执行插入、删除最小/最大值操作的场景，比如优先队列、堆排序等

二、斐波那契堆

1. 结构特点：
   斐波那契堆是一种由多个堆树（堆序树）组成的松散集合
   其结构更加复杂，但支持更高效的摊还时间复杂度
   斐波那契堆使用了一种懒惰的合并策略，在合并、删除、减少键值等操作时可以延迟一些整理工作，从而提高某些操作的效率
2. 操作复杂度（摊还分析）：
   插入元素：O(1)
   删除堆顶元素：O(log n)
   查找最小元素：O(1)
   合并：O(1)
   减少键值：O(1)
   删除任意元素：O(log n)
3. 使用场景：
   斐波那契堆特别适用于算法中 需要频繁合并堆 或者 减少键值的场景，例如Dijkstra算法的实现中使用斐波那契堆可以提高效率

总结：
二叉堆适合于简单、高效的场景，其实现和理解都相对容易，操作复杂度较稳定，常用于实际工程中
斐波那契堆 在特定场景下提供更优的时间复杂度，尤其是当需要 进行大量的合并和减少键值操作时，但其实现较为复杂，实际应用相对较少

1、最小生成树的形成

1、这个贪心策略 可以由下面的通用方法来表述。该通用方法 在每个时刻生长最小生成树的一条边，并在整个策略的实施过程中，管理一个 遵守下述循环不变式的边集合 A：

在每遍循环之前，A是某棵最小生成树的一个子集

在每一步，要做的事情是选择一条边 (u, v)，将其加入到集合 A 中，使得 A 不违反循环不变式，即 A ∪ { (u, v) } 也是某棵最小生成树的子集。由于 可以安全地将这种边加入到集合 A 而不会破坏 A 的循环不变式，因此称这样的边为 集合 A 的安全边

GENERIC-MST(G, w)
1 A=∅
2 while A does not form a spanning tree
3 	find an edge(u,v) that is safe for A
4 	A = A ∪ {(u,v)}
5 return A

奥妙是算法的第 3 行：找到一条安全边。这条安全边 必然存在，因为在执行算法第 3 行时，循环不变式告诉我们 存在一棵生成树 T，满足 A ⊆ T

无向图 G = (V, E) 的一个切割 (S, V-S) 是集合 V 的一个划分，如图23-2所示。如果一条边 (u, v) ∈ E 的一个端点位于集合 S，另一个端点位于集合 V - S，则称该条边横跨切割 (S, V-S)。如果集合 A 中不存在横跨该切割的边，则称 该切割尊重集合A

在横跨一个切割的所有边中，权重最小的边 称为轻量级边。注意，轻量级边 可能不是唯一的。一般，如果一条边是 满足某个性质的所有边中权重最小的，则称该条边是 满足给定性质的一条轻量级边

2、辨认安全边：
定理23.1 设 G = (V, E) 是一个在边E上定义了 实数值权重函数w的连通无向图。设集合 A 为 E（边） 的一个子集，且 A 包括在图G的某棵最小生成树中，设 (S, V-S) 是图G中尊重集合 A 的任意一个切割，又设 (u, v) 是横跨切割 (S, V-S) 的一条轻量级边。那么边 (u, v) 对于集合 A 来说是安全的

证明 设T是一棵包括 A 的最小生成树，并假定 T 不包含轻量级边 (u, v)；否则，已经证明完毕。现在来构建另一棵 最小生成树T’，通过剪切和粘贴来将 A ∪ {(u, v)} 包括在树 T’ 中，从而证明 (u, v) 对于集合 A 来说是安全的

边 (u, v) 与 T 中从结点 u 到结点 v 的简单路径 p 形成一个环路，如图23-3所示。由于结点 u 和结点 v 分别处在切割 (S, V-S) 的两端，T中至少有一条边属于简单路径 p 并且横跨该切割。设 (x, y) 为这样的一条边。因为切割 (S, V-S) 尊重集合 A，边 (x, y) 不在集合 A 中。由于边 (x, y) 位于 T 中从 u 到 v 的唯一简单路径上，将该边删除 会导致 T 被分解为两个连通分量。将 (u, v) 加进去可将 这两个连通分量连接起来 形成一棵新的生成树 T’ = T - {(x, y)} ∪ {(u, v)}

证明 T’ 是一棵 最小生成树。由于边 (u, v) 是横跨切割 (S, V-S) 的一条轻量级边，并且边 (x, y) 也横跨该切割，有 w(u, v) ≤ w(x, y)。因此
w(T’) = w(T) - w(x,y) + w(u,v) ≤ w(T)
T 是一棵最小生成树，有 w(T) ≤ w(T’)；因此，T’ 一定也是一棵最小生成树

还需要证明边 (u, v) 对于集合 A 来说是一条安全边。因为 A⊆T 并且 (x, y) ∉ A，所以有 A ⊆ T’；因此 A∪{(u, v)} ⊆ T’。由于 T’ 是最小生成树，(u, v) 对于集合 A 是安全的（可以安全地将这种边 加入到集合 A 而不会破坏 A 的循环不变式）

3、随着 GENERIC-MST 算法的推进，集合 A 总是保持在无环状态；否则，包含 A 的最小生成树 将包含一个环路，这将与树的定义相矛盾。在算法执行的任意时刻，图 G_A = (V, A) 是一个森林，G_A 中的每个连通分量则是一棵树（某些树可能仅包含一个结点，如在算法开始时，集合 A 为空，而森林中包含 |V| 棵树，每棵树中只有一个结点）。而且，由于 A∪{(u, v)} 必须是无环的，所有对于集合 A 为安全的边 (u,v) 所连接的是 G_A 中不同的连通分量

GENERIC-MST 算法的第 2～4 行的 while 循环执行的总次数为 |V|-1 次，因为该循环的每遍循环 都找出最小生成树所需 |V|-1 条边中的一条。在初始时，当 A=∅ 时，G_A 中有 |V| 棵树，每遍循环将树的数量减少 1 棵。当整个森林 仅包含一棵树时，该算法就终止

4、Kruskal 算法 和 Prim 算法 将使用定理 23.1 的下列推论
推论 23.2 设 G=(V, E) 是一个连通无向图，并有定义在边集合 E 上的实数值权重函数 w。设集合 A 为 E 的一个子集，且该子集包括在 G 的某棵最小生成树里，并设 C = (V_C, E_C) 为森林 G_A = (V, A) 中的一个连通分量（树）。如果边 (u, v) 是连接 C 和 G_A 中某个其他连通分量的一条轻量级边，则边 (u, v) 对于集合 A 是安全的

证明 切割 (V_C, V - V_C) 尊重集合 A（C为连通分量），边 (u, v) 是横跨该切割的一条轻量级边，因此，边 (u, v) 对于集合 A 是安全的

23.1-1 设 (u, v) 是连通图 G 中的一条权重最小的边，证明 边 (u, v) 为图 G 的某棵最小生成树中的一条边

反证法：
假设 (u, v) 不在某棵最小生成树 T 中。
构造一个新的生成树：
由于 T 是 G 的一棵生成树，不包含 (u, v)，所以 T 已经包含了 G 的所有顶点，并且有 n−1 条边（其中 n 是图 G 的顶点数）。加入边 (u, v)：如果 将边 (u, v) 加入 T，那么 T 中将形成一个环，因为现在 T 有 n 条边

在环中去掉一条边：
在这个环中，必定有一条边 e′ 是不必要的，因为 环中任意一条边的移除 不会影响生成树的连通性。由于 (u, v) 是图 G 中的最小权重边，所以 e′ 的权重 w(e′) 必定大于或等于 w(u, v)。

替换边：
如果我们从 T 中移除 e′，并用 (u, v) 替换 e′，那么新的边集仍然构成一棵生成树，并且由于 w(u, v) ≤ w(e′)，新的生成树的总权重不会比原来的生成树大。因此，新构造的树的总权重不超过原来的生成树 T

得出矛盾：
这就说明了，即使 (u, v) 不在最初的最小生成树 T 中，我们也可以通过构造一个包含 (u, v) 的生成树，使得其权重不大于 T 的权重。因此，假设 (u, v) 不在最小生成树中的前提是错误的

23.1-2 任意割的 轻量级边 都是安全边 !-> 安全边都是 任意割的 轻量级边
教授萨比耶尔提出了定理23.1的以下反命题。设$G=(V,E)$是一个连接的无向图，并且在边集$E$上定义了一个实值权重函数$w$。设$A$是$E$的一个子集，它包含在$G$的某个最小生成树中，设$S,V-S$是$G$的一个尊重$A$的割，且设$(u,v)$是$A$穿过$S,V-S$的一个安全边。则$(u,v)$是割的轻量级边。通过给出一个反例，证明教授萨比耶尔的猜想是错误的

设$G$为一个有$4$个顶点：$u,v,w,z$的图。设图的边为$(u,v)$, $(u,w)$, $(w,z)$，其权重分别为$3$，$1$和$2$
假设$A$是集合$(u,w)$。设$S=A$。则$S$明显尊重$A$。因为$G$是一棵树，它的最小生成树就是它本身，所以$A$显然是最小生成树的子集
因此，每条边都是安全的。特别地，$(u,v)$是安全的，但不是割的轻量级边。因此，萨比耶尔教授的猜想是错误的

安全边的定义：
对于一个图$G$的某个割$S,V-S$，如果一条边$(u,v)$是这个割中最小生成树的某条边，那么它被称为安全边。换句话说，如果你选择这条边，它不会阻止你构建最小生成树，并且它是必须要包括在最小生成树中的边

轻量级边的定义：
轻边是指在某个割$S,V-S$中，权重最小的边。也就是说，在所有穿过该割的边中，轻边的权重是最小的

在这个例子中，图$G$有四个顶点$u,v,w,z$，边的权重分别为：
$(u,v)$的权重为$3$，
$(u,w)$的权重为$1$，
$(w,z)$的权重为$2$
假设集合$A=(u,w)$，并且考虑割$S=u,w$和$V-S=v,z$。在这个割中，有两条边穿过割$S,V-S$，分别是$(u,v)$和$(w,z)$

为什么$(u,v)$是安全边？
$(u,v)$是图中唯一能将$v$连接到$u$或$w$的边，所以在构造最小生成树时，如果 要覆盖所有顶点，它是必不可少的，因此是安全的

为什么$(u,v)$不是轻量级边？
在割$S,V-S$中，穿过割的边有两条：$(u,v)$和$(w,z)$。其中，$(w,z)$的权重为$2$，而$(u,v)$的权重为$3$。根据轻量级边的定义，在这个割中，$(w,z)$的权重更小，所以$(w,z)$才是轻量级边，而不是$(u,v)$
但是如果看割：v以及u, w, z，那 (u, v) 就是 轻量级边

23.1-3
证明：如果一条边$(u,v)$包含在某个最小生成树中，那么它是 跨越图的 某个割（不是任意割） 的轻边

设 $T_0$ 和 $T_1$ 为通过从一个 $\text{MST}$（最小生成树）中移除边$(u,v)$后得到的两棵树。假设$V_0$和$V_1$分别是$T_0$和$T_1$的顶点。

考虑将$V_0$与$V_1$分开的割。假设存在一条权重比$(u,v)$更小的边在这个割中。那么，可以通过将该边加入到$T_1\cup T_0$中来构造整个图的一个最小生成树。这将导致一个权重比包含$(u,v)$的原始最小生成树更小的最小生成树

23.1-2 指定了特定的切割，而 23.1-3 没有

23.1-4
给出一个连通图的例子，使得边集合 {(u, v): 存在一个切割 (S, V−S)，使得 (u, v) 是横跨该切割的一条轻量级边 } 不形成一棵最小生成树

可能没有举完全 所有可能切割，也可能同一切割有多条轻量级边 都算上就有环了

23.1-5
设$e$是连通图$G=(V,E)$中某个环上的最大权重边。证明$G^{\prime }=(V,E-e)$的某棵最小生成树也是$G$的最小生成树。也就是说，存在$G$的一棵最小生成树不包含$e$

设$A$是一个割，它将环中的一些顶点分割到割的一侧，而将环中的其他顶点分割到另一侧。对于这些割中的任意一个，知道边$e$不是这个割的轻边。由于其他所有的割 都不会只有边$e$穿过，所以 不会有边$e$是这些割中的任何一个的轻边（因为是一个环）。这意味着边$e$不是安全的

23-1.6 如果一个图的每个割 都有唯一的轻边穿过该割，那么该图的最小生成树是唯一的

假设存在两个不同的最小生成树 T1 和 T2，找到不同的边：由于 T1 和 T2 是不同的，所以一定存在至少一条边 e 属于 T1，而不属于 T2，反之亦然
考虑边 e 的割：
在图中去掉 e 之后，T1 将被分成两个连通分量。设这个割为 S, V−S
割的性质：
根据题设，割 S, V−S 有且只有一条轻边穿过这个割。由于 e 是 T1 中的边，它必定是这个割的轻边（否则 T1 不可能是最小生成树）
矛盾：
由于 e 是唯一的轻边，它也必须出现在 T2 中，因为 T2 也必须包含所有的轻边来保证连通性和最小权重。但是这与 e 不属于 T2 的假设矛盾。因此，假设 T1 和 T2 是不同的最小生成树是错误的
结论：
这证明了图的最小生成树 是唯一的，如果每个割 都有唯一的轻边穿过

最小生成树的每一条边 都是 某一切割的轻量级边，最小生成树边 是 所有切割中 某一条轻量级边的集合

23-1.7 论证：如果一个图的所有边的权重 都是正数，那么任何连接所有顶点 且总权重最小的边的子集 必定是一棵树。举一个例子 来说明如果 允许一些权重为非正数，则这一结论不成立

首先，证明：连接所有顶点 且 总权重最小的边的子集是一棵树。为此，假设 它包含一个环。这意味着 移除环中的任何一条边，剩余的边 仍然可以连接所有顶点，但总权重会减少，因为 移除了某一条边的权重。这将 与子集总权重最小的性质相矛盾。因此，这个边的子集 必须是一棵树，并且由于它连接了所有顶点 且总权重最小，它也必须是最小生成树

为了说明这个结论在 允许负权重时不成立，给出一个构造。考虑图 K3，其中所有边的权重均为 −1。唯一的连接图的最小权重边集的总权重为 −3，并且由所有边组成。这显然不是一棵最小生成树，因为它不是一棵树（因为 比三顶点的树应该有的边数多一条）。任何此加权图的最小生成树的总权重 至少为 −2

23.1-8

23.1-9

23.1-10

2、Kruskal 算法和 Prim 算法

这两种算法 都是前一节所讨论的通用算法的细化，每种算法 都使用一条具体的规则 来确定 GENERIC-MST 算法第 3 行所描述的安全边

在 Kruskal 算法中，集合 A 是一个森林，其结点 就是给定图的结点。每次加入到集合 A 中的安全边 永远是权重最小的连接两个不同分量的边
在 Prim 算法里，集合 A 则是一棵树。每次加入到 A 中的安全边 永远是连接 A 和 A 之外某个结点的边中权重最小的边

2.1 Kruskal 算法

在所有连接森林中 两棵不同树的边里面，找到权重最小的边 (u, v)。设 C1 和 C2 为边 (u, v) 所连接的两棵树。由于边 (u, v) 一定是连接 C1 和 其他某棵树的一条轻量级边，推论 23.2 隐含告诉我们，边 (u, v) 是 C1 的一条安全边。Kruskal 算法属于贪心算法，因为 它每次都选择一条 权重最小的边加入到森林

使用一个 不相交集合数据结构 来维护几个互不相交的元素集合。每个集合 代表当前森林中的一棵树。操作 FIND-SET(u) 用来返回包含元素 u 的集合的代表元素。可以通过测试 FIND-SET(u) 是否等于 FIND-SET(v) 来判断结点 u 和结点 v 是否属于同一棵树

MST-KRUSKAL(G,w)
1 A=∅
2 for each vertex v∈G.V
3 	MAKE-SET(v)
4 sort the edges of G.E into nondecreasing order by weight w
5 for each edge (u,v)∈G.E, taken in nondecreasing order by weight
6 	if FIND-SET(u) ≠ FIND-SET(v)
7 		A = A ∪ {(u, v)}
8 		UNION(u,v)
9 return A

对于图 G=(V, E)，Kruskal 算法的运行时间依赖于 不相交集合数据结构的实现方式。假定使用 21.3 节所讨论的不相交集合森林实现，并增加 按秩合并和路径压缩的功能，因为 这是目前已知的渐近时间最快的实现方式

表示方式： 每个集合由一棵树表示，树的根节点表示整个集合，节点指向其父节点
路径压缩： 在执行Find操作时，通过将路径上的所有节点直接连接到根节点，从而平坦化树结构，这样后续操作能够更快地到达根节点
Find操作（带路径压缩）：

def find(x):if parent[x] != x:parent[x] = find(parent[x])  # 递归路径压缩return parent[x]

按秩合并： 在执行Union操作时，总是将秩（即树的高度）较小的树连接到秩较大的树，以避免增加树的高度
Union操作（按秩合并）：

def union(x, y):rootX = find(x)rootY = find(y)if rootX != rootY:if rank[rootX] > rank[rootY]:parent[rootY] = rootXelif rank[rootX] < rank[rootY]:parent[rootX] = rootYelse:parent[rootY] = rootXrank[rootX] += 1

在这种实现模式下，算法第 1 行对集合 A 的初始化时间为 O(1)，第 4 行对边进行排序的时间为 O(E lg E)（也可以写成 O(E α(V))）。算法第 5～8 行的 for 循环执行 O(E) 个 FIND-SET 和 UNION 操作。与 |V| 个 MAKE-SET 操作一起，这些操作的总运行时间为 O((V + E)α(V))，这里 α 是 21.4 节 所定义的一个增长非常缓慢的函数（MAKE-SET 操作的时间复杂度是 O(1)。FIND-SET 和 UNION 操作的均摊时间复杂度是 O(α(V))，其中 α(V) 是反阿克曼函数）

由于假定图 G 是连通的，因此有 |E| ≥ |V| - 1，所以不相交集合操作的时间代价为 O(Eα(V))。而且，由于 α(|V|) = O(lg V) = O(lg E)，Kruskal 算法的总运行时间为 O(E lg E)。如果再注意到 |E| < |V|²，则有 lg |E| = O(lg V)，因此，可以将 Kruskal 算法的时间重新表示为 O(E lg V)

2.2 Prim 算法

Prim 算法的工作原理 与 Dijkstra 的最短路径算法相似。Prim 算法 所具有的一个性质是 集合 A 中的边总是构成一棵树。如图 23-5 所示，这棵树 从一个任意的根结点 r 开始，一直长大到覆盖 V 中的所有结点时为止

算法每一步 在连接集合 A 和 A 之外的结点的所有边中，选择一条轻量级边 加入到 A 中。根据推论 23.2，这条规则所加入的边 都是对 A 安全的边。因此，当算法终止时，A 中的边形成 一棵最小生成树。本策略也属于贪心策略，因为每一步所加入的边 都必须是使树的总权重增加量最小的边

图 23-5 在图 23-1 上执行 Prim 算法的过程。初始的根结点为 a。加阴影的边和黑色的结点都属于树 A。在算法每一步，树中的结点就决定了图的一个切割，横跨该切割的一条轻量级边被加入到树中。例如，在图中的第 2 步，该算法可以选择将边 (b, c) 加入到树中，也可以选择将边 (a, h) 加入到树中，因为这两条边都是横跨该切割的轻量级边

为了有效地实现 Prim 算法，需要一种快速的方法 来选择一条新的边，以便加入到由集合 A 中的边所构成的树里。在下面的伪代码中，连通图 G 和 最小生成树的 根结点 r 将作为算法的输入
在算法的执行过程中，所有不在树 A 中的结点都存放在 一个基于 key 属性的最小优先队列 Q 中。对于每个结点 v，属性 v.key 保存的是连接 v 和 树中结点的所有边中最小边的权重。我们约定，如果不存在这样的边，则 v.key = ∞。属性 v.π 给出的是结点 v 在树中的父结点。Prim 算法将 GENERIC-MST 中的集合 A 维持在 A = {(v, v.π) : v∈V − {r} − Q} 的状态下

当 Prim 算法终止时，最小优先队列 Q 将为空，而 G 的最小生成树 A 则是：A = {(v, v.π) : v ∈ V − {r}}

MST-PRIM(G, w, r)
1 for each u ∈ G.V
2    u.key = ∞
3    u.π = NIL
4 r.key = 0
5 Q = G.V
6 while Q ≠ ∅
7    u = EXTRACT-MIN(Q)
8    for each v ∈ G.Adj[u]
9       if v ∈ Q and w(u, v) < v.key
10         v.π = u
11         v.key = w(u, v)

算法第 1~5 行将每个结点的 key 值设置为 ∞（除根结点 r 以外，根结点 r 的 key 值设置为 0，以便使该结点 成为第一个被处理的结点），将每个结点的父结点 设置为 NIL，并对最小优先队列 Q 进行初始化，使其包含图中所有的结点

该算法维持的循环不变式由 3 个部分组成：

1. A = {(v, v.π) : v ∈ V - {r} - Q}
2. 已经加入到最小生成树的结点为 集合 V - Q
3. 对于所有的结点 v ∈ Q，如果 v.π ≠ NIL，则 v.key < ∞ 并且 v.key 是连接结点 v 和最小生成树中某个结点的轻量级边 (v, v.π) 的权重

第 7 行将找出结点 u ∈ Q，该结点是某条横跨切割 (V - Q, Q) 的轻量级边的一个端点（第 1 次循环时例外，此时因为算法的第 4 行，所以有 u = r）。接着将结点 u 从队列 Q 中删除，并将其加入到集合 V - Q 中，也就是将边 (u, u.π) 加入到集合 A 中。算法第 8~11 行的 for 循环将每个与 u 邻接但不在树中的结点 v 的 key 和 π 属性进行更新，从而维持循环不变式的第 3 部分成立

Prim 算法的运行时间 取决于 最小优先队列 Q 的实现方式。如果将 Q 实现为一个二叉最小优先队列，可以使用 BUILD-MIN-HEAP 来执行算法的第 1~5 行，时间成本为 O(V)。while 循环中的语句一共要执行 |V| 次，由于每个 EXTRACT-MIN 操作需要的时间成本为 O(lgV)，EXTRACT-MIN 操作的总时间为 O(VlgV)。由于所有邻接链表的长度之和为 2|E|，算法第 8~11 行的 for 循环的总执行次数为 O(E)。在 for 循环里面，可以在常数时间内 完成对一个结点是否属于队列 Q 的判断，方法就是 对每个结点维护一个标志位来指明 该结点是否属于 Q，并在将结点从 Q 中删除的时候 对该标志位进行更新。算法第 11 行的赋值操作涉及一个隐含的 DECREASE-KEY 操作，该操作 在二叉最小堆上 执行的时间成本为 O(lgV)。因此，Prim 算法的总时间代价为 O(VlgV + ElgV) = O(ElgV)。从渐近意义上来说，它与 Kruskal 算法的运行时间相同

如果使用斐波那契堆 来实现最小优先队列 Q，Prim 算法的渐近运行时间 可以得到进一步的改善。如果斐波那契堆中有 |V| 个元素，则 EXTRACT-MIN 操作的时间摊还代价为 O(lgV)，而 DECREASE-KEY 操作（用于实现算法 第 11 行的操作）的摊还时间代价为 O(1)。因此，如果使用斐波那契堆来实现 最小优先队列 Q，则 Prim 算法的运行时间将改进到 O(E + VlgV)

使用二叉堆实现 Prim 算法的 C++ 代码

#include <iostream>
#include <vector>
#include <queue>
#include <climits>using namespace std;// 定义图的边结构，表示图中的一条边，包含目标顶点 to 和边的权重 weight
struct Edge {int to;int weight;
};// 定义优先队列的元素类型，包含顶点 vertex 和对应的 key 值。
// 重载了 > 运算符，以便使 priority_queue 可以按 key 值从小到大排序（最小堆）
struct Node {int vertex;int key;bool operator>(const Node &other) const {return key > other.key;  // 优先队列需要最小堆}
};//参数 start：Prim 算法的起始顶点。
// 参数 graph：图的邻接列表表示法。
// 该函数执行 Prim 算法，并输出最小生成树的边及其权重
void prim(int start, const vector<vector<Edge>> &graph) {int V = graph.size();vector<int> key(V, INT_MAX);   // 存储每个顶点到生成树的最小边权重vector<int> parent(V, -1);     // 存储最小生成树的父节点vector<bool> inMST(V, false);  // 判断顶点是否已加入到最小生成树// 优先队列（最小堆），用来选择权重最小的边priority_queue<Node, vector<Node>, greater<Node>> pq;// 初始化起始顶点key[start] = 0;pq.push({start, key[start]});while (!pq.empty()) {int u = pq.top().vertex;pq.pop();inMST[u] = true;  // 将顶点 u 包含到最小生成树中// 处理与 u 相连的所有边for (const auto &edge : graph[u]) {int v = edge.to;int weight = edge.weight;// 如果 v 不在最小生成树中，并且找到一个比当前 key 值更小的边if (!inMST[v] && key[v] > weight) {key[v] = weight;pq.push({v, key[v]});parent[v] = u;}}}// 输出最小生成树的边for (int i = 1; i < V; ++i) {if (parent[i] != -1) {cout << "Edge: " << parent[i] << " - " << i << " , Weight: " << key[i] << endl;}}
}int main() {int V = 5;  // 顶点数量vector<vector<Edge>> graph(V);// 添加边（无向图）graph[0].push_back({1, 2});graph[1].push_back({0, 2});graph[0].push_back({3, 6});graph[3].push_back({0, 6});graph[1].push_back({2, 3});graph[2].push_back({1, 3});graph[1].push_back({3, 8});graph[3].push_back({1, 8});graph[1].push_back({4, 5});graph[4].push_back({1, 5});graph[2].push_back({4, 7});graph[4].push_back({2, 7});// 调用 Prim 算法，从顶点 0 开始prim(0, graph);return 0;
}

使用斐波那契堆实现 Prim 算法的 C++ 代码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <limits.h>
#include <cmath>
#include <list>using namespace std;struct Node {int key;        // 顶点的键值int vertex;     // 顶点编号Node* parent;Node* child;Node* left;Node* right;int degree;bool marked;
};// 斐波那契堆
class FibonacciHeap {
private:Node* min;int n;public:FibonacciHeap() {min = nullptr;n = 0;}Node* insert(int vertex, int key) {Node* node = new Node();node->vertex = vertex;node->key = key;node->degree = 0;node->marked = false;node->parent = nullptr;node->child = nullptr;node->left = node;node->right = node;if (min != nullptr) {// 插入到根表中(min->left)->right = node;node->right = min;node->left = min->left;min->left = node;if (key < min->key) {min = node;}} else {min = node;}n++;return node;}Node* extractMin() {Node* z = min;if (z != nullptr) {if (z->child != nullptr) {Node* x = z->child;do {Node* next = x->right;// 将子节点 x 加入根表(min->left)->right = x;x->right = min;x->left = min->left;min->left = x;x->parent = nullptr;x = next;} while (x != z->child);}// 从根表中移除 z(z->left)->right = z->right;(z->right)->left = z->left;if (z == z->right) {min = nullptr;} else {min = z->right;consolidate();}n--;}return z;}void decreaseKey(Node* x, int k) {if (k > x->key) {cout << "Error: new key is greater than current key" << endl;return;}x->key = k;Node* y = x->parent;if (y != nullptr && x->key < y->key) {cut(x, y);cascadingCut(y);}if (x->key < min->key) {min = x;}}bool empty() {return min == nullptr;}private:void consolidate() {int D = (int)floor(log2(n)) + 1;vector<Node*> A(D, nullptr);vector<Node*> rootList;Node* x = min;do {rootList.push_back(x);x = x->right;} while (x != min);for (auto w : rootList) {Node* x = w;int d = x->degree;while (A[d] != nullptr) {Node* y = A[d];if (x->key > y->key) {swap(x, y);}link(y, x);A[d] = nullptr;d++;}A[d] = x;}min = nullptr;for (auto y : A) {if (y != nullptr) {if (min == nullptr) {min = y;} else {if (y->key < min->key) {min = y;}}}}}void link(Node* y, Node* x) {// 移除 y(y->left)->right = y->right;(y->right)->left = y->left;y->parent = x;if (x->child == nullptr) {x->child = y;y->right = y;y->left = y;} else {(x->child->left)->right = y;y->right = x->child;y->left = x->child->left;x->child->left = y;}x->degree++;y->marked = false;}void cut(Node* x, Node* y) {// 将 x 从 y 的子节点列表中移除if (x->right == x) {y->child = nullptr;} else {(x->left)->right = x->right;(x->right)->left = x->left;if (y->child == x) {y->child = x->right;}}y->degree--;// 将 x 加入到根表中(min->left)->right = x;x->right = min;x->left = min->left;min->left = x;x->parent = nullptr;x->marked = false;}void cascadingCut(Node* y) {Node* z = y->parent;if (z != nullptr) {if (!y->marked) {y->marked = true;} else {cut(y, z);cascadingCut(z);}}}
};void primFibonacci(int start, const vector<vector<pair<int, int>>>& graph) {int V = graph.size();vector<int> key(V, INT_MAX);vector<int> parent(V, -1);vector<Node*> nodePtrs(V, nullptr);FibonacciHeap minHeap;key[start] = 0;nodePtrs[start] = minHeap.insert(start, key[start]);while (!minHeap.empty()) {Node* minNode = minHeap.extractMin();int u = minNode->vertex;for (const auto& edge : graph[u]) {int v = edge.first;int weight = edge.second;if (nodePtrs[v] == nullptr) {nodePtrs[v] = minHeap.insert(v, weight);parent[v] = u;key[v] = weight;} else if (weight < key[v]) {minHeap.decreaseKey(nodePtrs[v], weight);parent[v] = u;key[v] = weight;}}}for (int i = 0; i < V; ++i) {if (parent[i] != -1) {cout << "Edge: " << parent[i] << " - " << i << " , Weight: " << key[i] << endl;}}
}int main() {int V = 5;  // 顶点数量vector<vector<pair<int, int>>> graph(V);// 添加边（无向图）graph[0].push_back({1, 2});graph[1].push_back({0, 2});graph[0].push_back({3, 6});graph[3].push_back({0, 6});graph[1].push_back({2, 3});graph[2].push_back({1, 3});graph[1].push_back({3, 8});graph[3].push_back({1, 8});graph[1].push_back({4, 5});graph[4].push_back({1, 5});graph[2].push_back({4, 7});graph[4].push_back({2, 7});// 调用 Prim 算法，从顶点 0 开始primFibonacci(0, graph);return 0;
}

22.2-3

22.2-4
假设一个图中的所有边权重都是从1到∣V∣范围内的整数。克鲁斯卡尔算法的运行速度可以有多快？如果边权重是从1到某个常数 W 的范围内的整数，情况会如何？

利用计数排序 对边进行排序，使用并查集结构来检测环的形成

def find(x):if parent[x] != x:parent[x] = find(parent[x])  # 递归路径压缩return parent[x]

3. Union操作（按秩合并）： 当合并两个集合时，我们将小树连接到大树上（按秩合并），以保持树的高度最小化。这进一步优化了Find操作的效率

def union(x, y):rootX = find(x)rootY = find(y)if rootX != rootY:if rank[rootX] > rank[rootY]:parent[rootY] = rootXelif rank[rootX] < rank[rootY]:parent[rootX] = rootYelse:parent[rootY] = rootXrank[rootX] += 1