最小生成树的例题及答案

最小生成树是一个在网络优化问题中经常被使用的算法，它是一种用于求解加权连通图的最小生成树的算法。

有两种经典的算法可以用于构建最小生成树，即 Kruskal 算法和 Prim 算法。在本文中，我们将介绍一个例题，并演示如何使用这些算法来求解它。

例题描述

在以下无向图中，边的权重表示两个顶点之间的距离。使用 Kruskal 算法和 Prim 算法分别求出该图的最小生成树。


解题过程

Kruskal 算法

Kruskal 算法是基于贪心的思想，它通过将边按照权重从小到大排序，然后逐个加入生成树的方法来构建最小生成树。具体的过程如下：

1. 把所有的边按照权值从小到大排序。

2. 按照排序后的顺序，依次考虑每一条边。

3. 如果这条边连接的两个顶点不在同一个连通块中，将它们合并到同一个连通块中，并将这条边加入生成树。

4. 重复步骤 3，直到生成树中有 n-1 条边为止。

使用 Kruskal 算法求解该题的具体步骤如下：

1. 将所有边按照权值从小到大排序，得到如下结果：

(E, C) 2

(A, C) 4

(A, D) 5

(B, C) 6

(C, F) 8

(D, E) 9

(C, E) 10

(F, G) 12

(D, G) 15

2. 从权值最小的边(E, C)开始，将它加入生成树；

3. 此时连通块为 {C, E}; 接着加入 (A, C) 与(A, D), 连通块变为 {A, C, D, E} ;

4. 加入 (B, C), 连通块变为{A, B, C, D, E};

5. 加入 (C, F)，连通块变为 {A, B, C, D, E, F}；

6. 加入 (D, E)，连通块不变，生成树变为:{(E, C), (A, C), (A, D), (B, C), (C, F), (D, E)}。

7. 加入 (C, E)，连接两个连通块，此时连通块变为{A, B, C, D, E, F, G}；生成树变为{(E, C), (A, C), (A, D), (B, C), (C, F), (C, E)}；

8. 加入最后一条边 (D, G)，生成树变为{(E, C), (A, C), (A, D), (B, C), (C, F), (C, E), (D, G)}。

此时，我们得到了该图的最小生成树。它的权值是 46。

Prim 算法

Prim 算法也是一种贪心算法。但是，不同于 Kruskal 算法，Prim 算法在处理边的时候是以顶点为基础的。具体过程如下：

1. 选择一个任意的起始顶点，并将其加入生成树中。(通常选择第一个顶点)

2. 将这个顶点的所有边按照权值从小到大排序，然后选取一条权值最小的边，并将连接到的顶点加入到生成树中。

3. 重复步骤 2 直到生成树中含有 n 个顶点为止。

同样，我们使用 Prim 算法求解该题的具体步骤如下：

1. 从顶点 A 开始，选择一个任意的起始顶点，将其加入到生成树中。

2. 将与顶点 A 相邻的边按照权值从小到大排序， 得到 (A, C) 4 和 (A, D) 5。

3. 选择权值最小的边 (A, C) , 并将顶点 C 加入到生成树中。

4. 将与顶点 C 相邻的边按照权值从小到大排序，得到 (C, E) 10 和 (C, B) 6。

5. 选择权值最小的边 (C, B) , 并将顶点 B 加入到生成树中。

6. 将与顶点 B 相邻的边按照权值从小到大排序，得到 (B, C) 6 和 (B, F) 7。

7. 选择权值最小的边 (B, C) , 并将顶点 E 加入到生成树中。

8. 将与顶点 E 相邻的边按照权值从小到大排序，得到 (E, C) 2，(E, D) 9和(E, F) 8。

9. 选择权值最小的边 (E, C) , 并将顶点 F 加入到生成树中。

10. 将与顶点 F 相邻的边按照权值从小到大排序，得到 (C, F) 8和(F, G) 12。

11. 选择权值最小的边 (C, F) , 并将顶点 G 加入到生成树中。

此时，我们同样得到了该图的最小生成树。它的权值是 46。