C++ 最小生成树问题：畅通工程 - Prim 和 Kruskal 算法实现

C++ 最小生成树问题：畅通工程 - Prim 和 Kruskal 算法实现

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府'畅通工程'的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

输入

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。

当N为0时，输入结束，该用例不被处理。

输出

对每个测试用例，在1行里输出最小的公路总长度。

样例输入

3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0

样例输出

3
5

算法1

(Prim 算法)

Prim 算法使用堆优化和邻接表的方法，可以在O(nlogn)的时间内解决最小生成树问题。

时间复杂度

O(nlogn)

参考文献

大话数据结构

C++ 代码

// Prim 算法代码示例

算法2

(Kruskal 算法)

Kruskal 算法是一种贪心算法，用来生成最小生成树。Kruskal 算法的基本思想是从小到大加入边，直到构建出来的边形成一个树为止。如果加入的边形成了环，那么就不加入这条边。

时间复杂度

O(nlogn)

参考文献

大话数据结构

C++ 代码

// Kruskal 算法代码示例