最小生成树演算法

习题预习

1. 最小生成树演算法是什么？它的定义是什么？

2. 什么是Kruskal演算法？它如何找到一个图的最小生成树？

3. 什么是Prim演算法？它如何找到一个图的最小生成树？

4. 什么是Boruvka演算法？它如何找到一个图的最小生成树？

5. Dijkstra演算法可以用来找到最短路径吗？如果可以，它如何实现？

说明知识

Minimum Spanning Tree Algorithms（最小生成树算法）是用来找寻一个连通无向图中，权值最小的生成树（即包含所有节点的树），其中权值可以是边的权重或是节点之间的距离。

以下是常被使用的Minimum Spanning Tree Algorithms：

1. Kruskal algorithm（克鲁斯卡尔算法）：将所有边依权值排序，从权值最小的边开始，依序加入生成树，直到所有节点都连通。

2. Prim’s algorithm（普利姆算法）：以一个起始点开始，找到离该点最近的一个连接节点加入生成树中，然后继续找到与生成树相连的最小的边，加入生成树中，直到所有节点都连通。

举例来说，假设有以下的无向图：

若采用Kruskal算法，最小生成树的边为：

若采用Prim算法，最小生成树的边为：

两种算法得到的最小生成树都是一样的，但是在不同的图形、节点数量上，两种算法的表现可能会有所不同。

条列重点

1. 最小生成树是一个无向图的生成树，它的边权值之和最小。
2. 最小生成树算法通常包括普里姆算法和克鲁斯卡尔算法。
3. 普里姆算法是从一个起点开始，每次选择与该点相邻且权值最小的边，将该点加入生成树，并将与该点相邻的边加入候选边集中，继续选择下一个节点直到所有点都在生成树中。
4. 克鲁斯卡尔算法是将边按权值从小到大排序，然后逐步加入生成树中，如果连接该边的两个点已经在生成树中，则忽略该边，否则加入生成树中。
5. 最小生成树算法的时间复杂度通常为O（ElogE），其中E为边数。

知识测验

1. 请实作 Kruskal 演算法找出下列图的最小生成树。
   
   答案：{(A, C), (C, D), (D, E), (E, F), (A, B)}

2. 请实作 Prim 演算法找出下列图的最小生成树。
   
   答案：{(A, D), (A, C), (C, B), (C, E), (E, F)}

3. 假设你有一个无向图，但是其中有些边是有向的，也就是说，你无法顺利的去走过那些只有单向的路段。请实现 Kruskal 演算法过滤掉所有无法双向通行的边，只找出仍可构成 MST 的边。
   答案： {(A, B), (B, C), (B, D), (D, F), (D, E)}

4. 请实作 Boruvka 演算法找出下列图的最小生成树。
   
   答案：{(A, B), (B, D), (C, D), (D, E), (E, F)}

5. 请将下列图例图使用 Kruskal 演算法找出最小生成树，但是加入特别的限制：所有的最短边都只能够使用一次，而非两次。
   
   答案：{(A, B), (B, C), (C, E), (C, F), (A, D)}