图的最小生成树算法--普里姆（Prim）算法和克鲁斯克尔（Kruskal）算法

一、图的最小生成树

最小生成树（Minimum spanning tree，MST）是最小权重生成树（Minimum weight spanning tree）的简称，是一个连通加权无向图中一棵权值最小的生成树。

在一给定的无向图 $G = (V, E)$ 中 $(u, v)$ 代表连接顶点 u 与顶点 v 的边 $\{ (u, v) | u \in V, v \in V \}$ ，而 $w (u, v))$ 代表此边的权重，若存在 $T$ 为 $E$ 的子集（即 $T\subseteq E$ ）且 $(V, T)$ 为树，使得：

$w(T)=\sum _{(u,v)\in T}w(u,v)$

的 $w (T)$ 最小，则此 T 为 G 的最小生成树。

一个连通图可能有多个生成树。当图中的边具有权值时，总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言，对于非连通无向图来说，它的每一连通分量同样有最小生成树，它们的并被称为最小生成森林。

最小生成树在一些情况下可能会有多个。例如，当图的每一条边的权值都相同时，该图的所有生成树都是最小生成树。
如果图的每一条边的权值都互不相同，那么最小生成树将只有一个。

如下加权无向连通图

在这里插入图片描述
其最小成生树为：

和

求取一张无向图的最小生成树的算法主要有普里姆（Prim）算法个克鲁斯克尔（Kruskal）算法。

二、普里姆（Prim）算法

普里姆算法（Prim Algorithm）是图论中的一种贪心算法，可在一个加权连通图中找到其最小生成树。

1. 算法简介

该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（Robert C. Prim）独立发现；1959年，艾兹赫尔·韦伯·迪杰斯特拉（Edsger W. Dijkstra）再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。

2. 算法思想与步骤

算法思想：从某⼀个顶点开始构建⽣成树；每次将代价最⼩的新顶点纳⼊⽣成树，直到所有顶点都纳⼊为⽌。

算法步骤：
输入：一个加权连通图，其中顶点集合为 $V$ ，边集合为 $E$ ；
输出：使用集合 $V_{\text{new}}$ 和 $E_{\text{new}}$ 来描述所得到的最小生成树。
初始化： $V_{\text{new}}=\{x\}$ ，其中 $x$ 为集合 $V$ 中的任一节点（起始点）， $E_{\text{new}}=\{\}$ 。

在集合 $E$ 中选取权值最小的边 $(u,v)$ ，其中 $u$ 为集合 $V_{\text{new}}$ 中的元素，而 $v$ 则是 $V$ 中没有加入 $V_{\text{new}}$ 的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
将 $v$ 加入集合 $V_{\text{new}}$ 中，将 $(u,v)$ 加入集合 $E_{\text{new}}$ 中；
重复步骤1到步骤2，直到 $V_{\text{new}}=V$ 。

下图为普里姆（Prim）算法的一个例子：
在这里插入图片描述
上图是一个 $V=\{v_0,v_1,v_2,v_3,v_4,v_5\}$ 的无向图，使用Prim算法计算最小生成树。

首先进行初始化操作，任选一个顶点作为初始顶点，本例子中选择 $v_0$ ，即：将 ${v_0}$ 加入到 $V_{new}$ ，此时 ${V_{new}=\{v_0\}}$ ；
其次以 ${V_{new}=\{v_0\}}$ 为基准，寻找与 $v_0$ 相邻，边的权值最小的顶点，可以发现边 $v_0, v_3)$ 的权值 $w_{03}$ 为1，是最小的，所以连通 $v_0$ 与 $v_3$ ，即：将 ${v_3}$ 加入到 $V_{new}$ 并将 $v_0, v_3)$ 加入到 $E_{new}$ 此时 ${V_{new}=\{v_0，v_3\}}$ ， ${E_{new}=\{(v_0, v_3)\}}$ ；
然后以 ${V_{new}=\{v_0，v_3\}}$ 中的两个顶点一起作为基准，发现相邻的顶点中边 $v_2, v_3)$ 的权值 $w_{23}$ 为4，是最小的，所以连通 $v_2$ 与 $v_3$ ，即：将 ${v_2}$ 加入到 $V_{new}$ 并将 $v_2, v_3)$ 加入到 $E_{new}$ ，此时 ${V_{new}=\{v_0,v_2,v_3\}}$ ， ${E_{new}=\{(v_0, v_3),(v_2, v_3)\}}$ ；
接下来以 ${V_{new}=\{v_0,v_2,v_3\}}$ 作为基准，权值 $w_{25}$ 为2，是最小的一条边，连通边 $v_2, v_5)$ ，即：将 ${v_5}$ 加入到 $V_{new}$ 并将 $v_2, v_5)$ 加入到 $E_{new}$ ，此时 ${V_{new}=\{v_0,v_2,v_3, v_5\}}$ ， ${E_{new}=\{(v_0, v_3), (v_2, v_3),(v_2, v_5)\}}$ ；
以 ${V_{new}=\{v_0，v_2,v_3, v_5\}}$ 作为基准， $w_{13}$ 为5，连通边 $v_1, v_3)$ ，即：将 ${v_1}$ 加入到 $V_{new}$ 并将 $v_1, v_3)$ 加入到 $E_{new}$ ，此时 ${V_{new}=\{v_0,v_1,v_2,v_3, v_5\}}$ ， ${E_{new}=\{(v_0, v_3), (v_2, v_3),(v_2, v_5),(v_1, v_3)\}}$ ；
最后连通权值为4的边 $v_1, v_4)$ ，即：将 ${v_4}$ 加入到 $V_{new}$ 并将 $v_1, v_4)$ 加入到 $E_{new}$ ，此时 ${V_{new}=\{v_0,v_1,v_2,v_3,v_4, v_5\}}$ ， ${E_{new}=\{(v_0, v_3), (v_2, v_3),(v_2, v_5),(v_1, v_3),(v_1, v_4)\}}$
对比发现此时 ${V_{new}=V}$ ，即说明所有节点都已经连通了，最小生成树计算完毕。

经过以上步骤，通过Prim算法得到了无向图 $V=\{v_0,v_1,v_2,v_3,v_4,v_5\}$ 的最小生成树。

三、克鲁斯克尔（Kruskal）算法

克鲁斯克尔算法（英语：Kruskal algorithm）是一种用来查找最小生成树的算法，是贪心算法的应用。

1. 算法简介

克鲁斯克尔算法由美国数学家约瑟夫·克鲁斯克尔（Joseph Bernard Kruskal, Jr.）在1956年发表。贪心算法的应用，克鲁斯克尔算法在图中存在相同权值的边时也有效。

2. 算法思想与步骤

算法思想：每次选择⼀条权值最⼩的边，使这条边的两头连通（原本已经连通的就不选），直到所有结点都连通。

算法步骤：

新建图 $G$ ， $G$ 中拥有原图中相同的节点，但没有边；
将原图中所有的边按权值从小到大排序；
从权值最小的边开始，如果这条边连接的两个节点于图 $G$ 中不在同一个连通分量中，则添加这条边到图 $G$ 中；
重复3，直至图 $G$ 中所有的节点都在同一个连通分量中。

下图为克鲁斯克尔（Kruskal）算法的一个例子：
在这里插入图片描述
上图是一个 $V=\{v_0,v_1,v_2,v_3,v_4,v_5\}$ 的无向图，使用Kruskal算法计算最小生成树。

首先按照权值将所有的边进行排序，按照顺序的集合 $E_{order} =\{(v_0, v_3),(v_2, v_5),(v_1, v_4),(v_2, v_3),(v_3, v_5),(v_0, v_2),(v_1, v_3),(v_0, v_1),(v_3, v_4),(v_4, v_5)\}$ ，将集合中按照权值排序好点按照顺序一次检查是否符合连通条件。
首先检查发现加入顶点 $v_0$ 和 $v_3$ 的边 $v_0, v_3)$ 后不会构成回路，即当前顶点 $v_0$ 和 $v_3$ 不在同一个连通分量中，则可以将顶点 $v_0$ 和 $v_3$ 连起来，即 $E_{new} =\{(v_0, v_3)\}$ ；
依次检查发现加入顶点 $v_2$ 和 $v_3$ 的边 $v_2, v_3)$ 后不会构成回路，即当前顶点 $v_2$ 和 $v_3$ 不在同一个连通分量中，则可以将顶点 $v_2$ 和 $v_3$ 连起来，即 $E_{new} =\{(v_0, v_3),(v_2, v_5)\}$ ；
依次检查发现加入顶点 $v_1$ 和 $v_4$ 的边 $v_1, v_4)$ 后不会构成回路，即当前顶点 $v_1$ 和 $v_4$ 不在同一个连通分量中，则可以将顶点 $v_1$ 和 $v_4$ 连起来，即 $E_{new} =\{(v_0, v_3),(v_2, v_5),(v_1, v_4)\}$ ；
依次检查发现加入顶点 $v_2$ 和 $v_3$ 的边 $v_2, v_3)$ 后不会构成回路，即当前顶点 $v_2$ 和 $v_3$ 不在同一个连通分量中，则可以将顶点 $v_2$ 和 $v_3$ 连起来，即 $E_{new} =\{(v_0, v_3),(v_2, v_5),(v_1, v_4),(v_2, v_3)\}$
依次检查发现加入顶点 $v_3$ 和 $v_5$ 的边 $v_3, v_5)$ 后会构成回路，即当前顶点 $v_3$ 和 $v_5$ 在同一个连通分量中，则不能将顶点 $v_3$ 和 $v_5$ 连起来；
依次检查发现加入顶点 $v_0$ 和 $v_2$ 的边 $v_0, v_2)$ 后会构成回路，即当前顶点 $v_0$ 和 $v_2$ 在同一个连通分量中，则不能将顶点 $v_0$ 和 $v_2$ 连起来；
依次检查发现加入顶点 $v_1$ 和 $v_3$ 的边 $v_1, v_3)$ 后不会构成回路，即当前顶点 $v_1$ 和 $v_3$ 不在同一个连通分量中，则可以将顶点 $v_1$ 和 $v_3$ 连起来，即 $E_{new} =\{(v_0, v_3),(v_2, v_5),(v_1, v_4),(v_2, v_3),(v_1, v_3)\}$
此时所有顶点均已处于同一个连通分量中，再连上任意一条边都会形成回路，所以最小生成树计算完毕！

四、普里姆（Prim）算法对比克鲁斯克尔（Kruskal）算法

算法思想：
- 普里姆（Prim）算法：从某⼀个顶点开始构建⽣成树；每次将代价最⼩的新顶点纳⼊⽣成树，直到所有顶点都纳⼊为⽌。
- 克鲁斯克尔（Kruskal）算法：每次选择⼀条权值最⼩的边，使这条边的两头连通（原本已经连通的就不选）直到所有结点都连通
时间复杂度：
- 普里姆（Prim）算法： $O(|V|^2 )$
- 克鲁斯克尔（Kruskal）算法： $O( |E|log_2 |E| )$
适用范围：
- 普里姆（Prim）算法：适合⽤于边稠密图
- 克鲁斯克尔（Kruskal）算法：适合⽤于边稀疏图