6.8.最小生成树

---

一.复习：

1.生成树：

对于一个连通的无向图，假设图中有n个顶点，如果能找到一个符合以下要求的子图：

子图中包含图中所有的顶点，同时各个顶点保持连通，

而且子图的边的数量只有n-1条，

那么这样的子图就是生成树，一个连通图可能有多个生成树。

2.广度优先生成树：

3.深度优先生成树：

---

二.最小生成树（最小代价树）：生成树必须包含图中所有的顶点

1.前言：

假设有一个城市叫P城，P城周围规划了学校、农场、电站、渔村、矿场，

各个地方之间有上图所示的修路方案，其中数字表示修路的成本，比如修一条P城和学校之间的路需要1块钱，修一条学校和矿场之间的路需要5块钱，

现在为了节省P城的财政支出，没有必要把所有的可行的道路都修一遍，

因此需要制定一个修路方案，这个方案要求所有地方都是连通的即各个地方之间是相互可到达的（各个地方之间不一定是相邻的），但是成本又必须降到最低，此时有如下两种方案：

左边的方案可以使得各个地方连通，代价是20块钱（图片打错了）；

右边的方案也可以使各个地方连通，但代价是16块钱，

但是否有更便宜的方案呢？这就是最小生成树（最小代价树）要研究的问题。

对于带权的连通图，它可以有多个生成树，我们要从所有的生成树当中找出各个边的权值之和最小即代价最小的那棵树，这个树就是最小生成树。

2.概念：

注：最小生成树研究的是带权的连通无向图。

3.特例：当带权连通的无向图的权值都为一个数

以上述图片的带权连通无向图为例，可得出如下两个生成树：

由生成树的概念可知这两棵生成树的边都是5条（边等于顶点总数减一，此时有6个顶点），由于每一条边的权值都为1，因此这两棵生成树所有边的权值之和都为5，

由此可知本例中带权无向图的任意一棵生成树的所有边的权值之和都为5，因此最小的权值之和为5，

结论：假设一个带权连通无向图的顶点数为V个，边为E条，边的权值都为a，

该图的所有生成树都只有(V-1)条边，其权值之和为(V-1) * a，由此可知最小生成树的权值之和为(V-1) * a，因为所有树都一样。

4.性质：

• 如果一个连通图本身就是一棵树（树不存在环路），也就是图中各个顶点连通但不存在环，那么这个图的最小生成树就是它本身->因为如果连通图是树时，那么它已经是生成树了，而且无法再有更小的生成树了，再有的话就会缺顶点，不符合生成树的条件，所以此时这个图的最小生成树就是它本身

• 只有连通图才有生成树

• 对于非连通图，只会有生成森林，因为非连通图不止一个连通分量，生成的也就不止一个生成树，最终就是生成森林（这里生成必须要包括图中的所有顶点，不然不符合生成的条件）

5.总结：

---

三.求最小生成树-Prim算法(普里姆算法)：

1.例一：

以上述图片为例，挑选图中任意一个顶点，从该顶点出发构建生成树：

如上图，比如从P城这个顶点出发构建生成树，之后每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止，

此时要构建的生成树中只有P城这一个顶点，从P城出发，分别对比到达学校、矿场、渔村、电站、农场所需要的代价，可知从P城到达学校的代价最小，因此接下来要把学校这个顶点纳入生成树，如下图：

如上图，在当前生成树下重复刚才的步骤，此时的生成树中有P城和学校两个顶点，

现在要从P城或学校出发，在农场、电站、渔村、矿场中选择一个代价最小的顶点连到当前生成树中，

由上图可知最小的代价为4，如下图：

意味着可以把矿场或者渔村纳入生成树中，

此时先把矿场纳入生成树，如下图：

如上图，在当前生成树下重复刚才的步骤，此时的生成树中包括P城、学校和矿场，

现在要从P城或学校或矿场出发，在农场、电站、渔村中选择一个代价最小的顶点连到当前生成树中，

由上图可知最小的代价为2，如下图：

意味着把渔村纳入生成树中，如下图：

如上图，在当前生成树下重复刚才的步骤，此时的生成树中包括P城、学校、矿场和渔村，

现在要从P城或学校或矿场或渔村出发，在农场、电站中选择一个代价最小的顶点连到当前生成树中，

由上图可知最小的代价为5，如下图：

意味着把农场纳入生成树中，如下图：

如上图，在当前生成树下重复刚才的步骤，此时的生成树中包括P城、学校、矿场、渔村和农场，

现在要从P城或学校或矿场或渔村或农场出发，在电站中选择一个代价最小的顶点连到当前生成树中，

由上图可知最小的代价为3，如下图：

意味着把电站纳入生成树中，如下图：

如下图，最终得到了最小生成树：

也就是说按照如上图所得出的最小生成树进行施工的话，只需要付15块钱，也是最小代价。

2.例二：

以上述图片为例，挑选图中任意一个顶点，从该顶点出发构建生成树：

如上图，比如从P城这个顶点出发构建生成树，之后每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止，

此时要构建的生成树中只有P城这一个顶点，从P城出发，分别对比到达学校、矿场、渔村、电站、农场所需要的代价，可知从P城到达学校的代价最小，因此接下来要把学校这个顶点纳入生成树，如下图：

如上图，在当前生成树下重复刚才的步骤，此时的生成树中有P城和学校两个顶点，

现在要从P城或学校出发，在农场、电站、渔村、矿场中选择一个代价最小的顶点连到当前生成树中，

由上图可知最小的代价为4，如下图：

意味着可以把矿场或者渔村纳入生成树中，

此时把渔村纳入生成树，如下图：

如上图，在当前生成树下重复刚才的步骤，此时的生成树中包括P城、学校、渔村，

现在要从P城或学校或渔村出发，在农场、电站、矿场中选择一个代价最小的顶点连到当前生成树中，

由上图可知最小的代价为2，如下图：

意味着把矿场纳入生成树中，如下图：

如上图，在当前生成树下重复刚才的步骤，此时的生成树中包括P城、学校、渔村、矿场，

现在要从P城或学校或渔村或矿场出发，在农场、电站中选择一个代价最小的顶点连到当前生成树中，

由上图可知最小的代价为5，如下图：

意味着把农场纳入生成树中，如下图：

如上图，在当前生成树下重复刚才的步骤，此时的生成树中包括P城、学校、渔村、矿场、农场，

现在要从P城或学校或渔村或矿场或农场出发，在电站中选择一个代价最小的顶点连到当前生成树中，

由上图可知最小的代价为3，如下图：

意味着把电站纳入生成树中，如下图：

如下图，最终得到了最小生成树：

也就是说按照如上图所得出的最小生成树进行施工的话，只需要付15块钱，也是最小代价。

3.对比例一与例二分别得出的最小生成树：

以上两棵生成树的最小代价都是15，

因此同一个图可能有多个最小生成树，虽然形态不同，但是这些最小生成树的所有边的权值之和都是一样且最小的。

4.例三：

以上述图片为例，挑选图中任意一个顶点，从该顶点出发构建生成树：

如上图，比如从农场这个顶点出发构建生成树，之后每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止，

此时要构建的生成树中只有农场这一个顶点，从农场出发，分别对比到达学校、电站、渔村、矿场、P城所需要的代价，可知从农场到达电站的代价最小，因此接下来要把电站这个顶点纳入生成树，如下图：

如上图，在当前生成树下重复刚才的步骤，此时的生成树中有农场和电站两个顶点，

现在要从农场或电站出发，在渔村、矿场、学校、P城中选择一个代价最小的顶点连到当前生成树中，

由上图可知最小的代价为5，如下图，因此要把P城纳入生成树中：

如上图，在当前生成树下重复刚才的步骤，此时的生成树中有农场、电站、P城，

现在要从农场或电站或P城出发，在渔村、矿场、学校中选择一个代价最小的顶点连到当前生成树中，

由上图可知最小的代价为1，如下图，因此要把学校纳入生成树中：

如上图，在当前生成树下重复刚才的步骤，此时的生成树中有农场、电站、P城、学校，

现在要从农场或电站或P城或学校出发，在渔村、矿场中选择一个代价最小的顶点连到当前生成树中，

由上图可知最小的代价为4，如下图，因此可以把矿场或渔村纳入生成树中，此时把矿场纳入生成树中（这里把渔村纳入生成树后得出的最小生成树的最小代价一致）：

如上图，在当前生成树下重复刚才的步骤，此时的生成树中有农场、电站、P城、学校、矿场，

现在要从农场或电站或P城或学校或矿场出发，在渔村中选择一个代价最小的顶点连到当前生成树中，

由上图可知最小的代价为2，如下图，因此可以把渔村纳入生成树中：

最终得出了如上图所示的最小生成树，最小代价也是15，与例一、例二的最小代价一样。

---

四.求最小生成树-Kruskal算法(克鲁斯卡尔)：

实例：

执行过程：每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选），直到所有顶点连通。

以上述图片为例，一开始图里的各个顶点都独立存在，各个顶点之间不存在边，所以用虚线标注，

现在从所有的虚线里挑出权值最小的一条，显然权值最小的是1这条虚线，如下图：

如上图，1这条虚线的两头是P城和学校这两个顶点，这两个顶点此时还没有连通，所以把这条虚线选中，使这两个顶点连通，如下图：

如上图，继续从所有的虚线里挑出权值最小的一条，显然权值最小的是2这条虚线，如下图：

如上图，2这条虚线的两头是渔村和矿场这两个顶点，这两个顶点此时还没有连通，所以把这条虚线选中，使这两个顶点连通，如下图：

如上图，继续从所有的虚线里挑出权值最小的一条，显然权值最小的是3这条虚线，如下图：

如上图，3这条虚线的两头是农场和电站这两个顶点，这两个顶点此时还没有连通，所以把这条虚线选中，使这两个顶点连通，如下图：

如上图，继续从所有的虚线里挑出权值最小的一条，显然权值最小的是4这条虚线，如下图：

如上图，P城和矿场之间的虚线的权值、P城和渔村之间的虚线的权值都为4，现在选择P城和矿场之间的虚线，P城和矿场这两个顶点此时还没有连通，所以把这条虚线选中（P城和渔村这两个顶点此时也没有连通，所以选这条虚线也可以），使这两个顶点连通，最终P城、矿场、渔村、学校这几个顶点就都连通了，如下图：

如上图，继续从所有的虚线里挑出权值最小的一条，显然权值最小的是4这条虚线，如下图：

如上图，此时权值为4的这条虚线的两头是P城和渔村，由于P城和渔村这两个顶点已经连通了，所以这条虚线需要跳过不选，如下图：

如上图，继续从所有的虚线里挑出权值最小的一条，显然权值最小的是5这条虚线，如下图：

如上图，P城和农场之间的虚线的权值、学校和矿场之间的虚线的权值都为5，由于学校和矿场已经连通，因此学校和矿场之间的虚线不选，而P城和农场之间还没有连通，所以应选中P城和农场之间的虚线，如下图：

如上图，至此，所有的顶点全部连通，Kruskal算法(克鲁斯卡尔)结束。

如下图，本例采用Kruskal算法(克鲁斯卡尔)得出的最小生成树的最小代价为15，与用Prim算法(普里姆算法)得出的结果一致：

---

五.Prim算法(普里姆算法) v.s. Kruskal算法(克鲁斯卡尔)：

假设图中有V个顶点、E条边：

对于Prim算法(普里姆算法)，每一次是选择一个顶点开始；

对于Kruskal算法(克鲁斯卡尔)，每一次是选择一条边开始；

因此这两个算法所表现出的时间复杂度也就不一样，

Prim算法(普里姆算法)的时间复杂度只与顶点的个数有关，适用于边稠密图即边多的图（因为边多的话顶点相对少一些），

Kruskal算法(克鲁斯卡尔)的时间复杂度只与边的个数有关，适用于边稀疏图即边少的图（因为边越少越能在短时间完成）。

---

六.Prim算法的实现思想：

1.实例：

以上述图片为例，假设从v0顶点开始，设置isJoin数组和lowCost数组：

isJoin数组用于记录图中的顶点是否被加入正在组建的生成树中，由于刚开始v0已经在生成树中，所以v0在isJoin数组的值为true（上述图片标记为勾），其余的顶点没有加入生成树中，因此其余的顶点对应的值都为false（上述图片标记为叉）；

lowCost数组用于记录把这些顶点加入到已经组建的生成树里所需要花费的最低代价->最开始选中了v0，

由于v0与v0之间不存在边，所以v0对应的lowCost数组的值为0，

由于v0与v1之间有一条边，这条边的权值为6，因此把v1加入到组建的生成树中所需要付出的最低代价是6，所以v1对应的lowCost数组的值为6，

由于v0与v2之间有一条边，这条边的权值为5，因此把v3加入到组建的生成树中所需要付出的最低代价是5，所以v2对应的lowCost数组的值为5，

由于v0与v3之间有一条边，这条边的权值为1，因此把v2加入到组建的生成树中所需要付出的最低代价是1，所以v3对应的lowCost数组的值为1，

而v4与v5这两个顶点和v0之间都没有直接相连的边，所以就目前来看，暂时无法把v4、v5放到组建好的生成树中，因此v4与v5对应的lowCost的值都用无穷记录，也可以用别的记录。

如下图，开始进行第一轮处理：

首先需要检查isJoin数组和lowCost数组，最终找出一个还没有被加入生成树且代价最低的顶点，

由上述图片可知，v3顶点没有加入生成树中且代价最小，因此把v3顶点加入生成树中，如下图：

如上图，要把v3顶点在isJoin数组中对应的值修改为true即勾，表示已加入生成树中，继续如下图：

如上图，需要循环遍历lowCost数组，更新还没加入的各个顶点对应的lowCost值，

现在加入了v3这个顶点之后，对于其他的还没有被加入生成树的顶点，接下来加入生成树的代价有可能会改变，

因为生成树中相较于一开始多了个v3顶点，最开始只有v0顶点时加入v1顶点最低代价为6，现在多了个v3顶点，加入v1顶点的最低代价为5，显然小于6，因此接下来如果要把v1加到生成树中，所需要付出的最低代价就从6变成了5，

因此把v1对应的lowCost值修改为5，同理现在

加入v2的最低代价为4，因此把v2对应的lowCost值修改为4，

加入v4的最小代价为6，因此把v4对应的lowCost值修改为6，

加入v5的最小代价为4，因此把v5对应的lowCost值修改为4，

由于v0与v3这两个顶点已经加入到生成树中，所以对应的lowCost值无需修改（因为之后不会再加入v0与v3这两个顶点），

最终lowCost数组中的值依次为0、5、4、1、6、4，

如下图：

如下图，开始进行第二轮处理：原理与第一轮一样

首先需要检查isJoin数组和lowCost数组，最终找出一个还没有被加入生成树且代价最低的顶点，

由上述图片可知，v2顶点和v5顶点都没有加入生成树中且代价都是最小的（代价都为4），因此v2顶点和v5顶点都可以加入生成树中，但如果是从头到尾去扫描lowCost数组中的元素，v2顶点是第一个被挑选并加入生成树中的，如下图：

如上图，要把v2顶点在isJoin数组中对应的值修改为true即勾，表示已加入生成树中，继续如下图：

如上图，需要循环遍历lowCost数组，更新还没加入的各个顶点对应的lowCost值，

由上述图片可知，加入v2顶点之后，

加入v1的最低代价为5，无需修改，

加入v4的最小代价为6，无需修改，

加入v5的最小代价为2，因此把v5对应的lowCost值修改为2，

由于v0、v3和v2这三个顶点已经加入到生成树中，所以对应的lowCost值无需修改（因为之后不会再加入v0、v3和v2这三个顶点），

最终lowCost数组中的值依次为0、5、4、1、6、2，

如下图：

如下图，开始进行第三轮处理：

首先需要检查isJoin数组和lowCost数组，最终找出一个还没有被加入生成树且代价最低的顶点，

由上述图片可知，v5顶点没有加入生成树中且代价最小，因此把v5顶点加入生成树中，如下图：

如上图，要把v5顶点在isJoin数组中对应的值修改为true即勾，表示已加入生成树中，继续如下图：

如上图，需要循环遍历lowCost数组，更新还没加入的各个顶点对应的lowCost值，

由上述图片可知，加入v5顶点之后，

加入v1的最低代价为5，无需修改，

加入v4的最小代价为6，无需修改，

由于v0、v3、v2和v5这四个顶点已经加入到生成树中，所以对应的lowCost值无需修改（因为之后不会再加入v0、v3、v2和v5这四个顶点），

最终lowCost数组中的值依次为0、5、4、1、6、2，

如下图：

如下图，开始进行第四轮处理：

首先需要检查isJoin数组和lowCost数组，最终找出一个还没有被加入生成树且代价最低的顶点，

由上述图片可知，v1顶点没有加入生成树中且代价最小，因此把v1顶点加入生成树中，如下图：

如上图，要把v1顶点在isJoin数组中对应的值修改为true即勾，表示已加入生成树中，继续如下图：

如上图，需要循环遍历lowCost数组，更新还没加入的各个顶点对应的lowCost值，

由上述图片可知，加入v1顶点之后，

加入v4的最小代价为3，因此把v4对应的lowCost值修改为2，

由于v0、v3、v2、v5和v1这五个顶点已经加入到生成树中，所以对应的lowCost值无需修改（因为之后不会再加入v0、v3、v2、v5和v1这五个顶点），

最终lowCost数组中的值依次为0、5、4、1、3、2，

如下图，开始进行第五轮处理：

首先需要检查isJoin数组和lowCost数组，最终找出一个还没有被加入生成树且代价最低的顶点，

由上述图片可知，v4顶点没有加入生成树中且代价最小，因此把v4顶点加入生成树中，如下图：

如上图，要把v4顶点在isJoin数组中对应的值修改为true即勾，表示已加入生成树中，

最终所有顶点全部加入到生成树中，Prim算法结束。

2.时间复杂度分析：

上述例子中进行了好几轮的处理最终得出最小生成树，从代码角度来看就是好几轮的循环，

由于每一轮的循环都会选择一个新的顶点把它放入生成树中，假设图中有n个顶点就需要n-1轮的循环，因为第一个顶点不需要循环，

而每一轮的处理当中又需要进行两次循环遍历，第一次循环遍历所有的顶点来从isJoin数组和lowCost数组中找出未加入生成树且代价最小的顶点，第二次循环遍历所有的顶点来更新lowCost数组，所以每一轮的时间复杂度为O(2n)，等价于O(n)，

由于需要n-1轮循环，所以总的时间复杂度就是O( n * (n-1) )，等价于O( n * n - n )，等价于O( n * n )，

如果改为图中有V个顶点，时间复杂度就是O( |V| * |V|)。

---

七.Kruskal算法(克鲁斯卡尔)的实现思想：

1.实例：

如下图，由于Kruskal算法(克鲁斯卡尔)每次要选择一条权值最小的边，所以要先把各条边按照权值递增的次序进行排序：

如上图，权值最小的边是权值为1的这条边，两边的顶点是v0和v3，所以上述图片里的第一行数据中weight为1、Vertex1为v0、Vertex2为v3，该算法的执行过程就是把所有的边都检查一遍。

如上图，第一条边的权值为1，两边连的顶点是v0和v3，接下来就要检查v0和v3是否连通，进行这个判断用到了并查集（详情见"5.15.并查集"），大致的思想就是刚开始要把所有的顶点分别看作是不同的集合，所以对于第一条边的两个顶点v0和v3，他们刚开始从属于不同集合，也就意味着他们此时不连通，因此就可以把这条边选中，如下图：

此时v0和v3这两个顶点就属于同一个集合了，

如下图，接下来进行第二轮的处理，权值为2的边的两头为v2和v5，v2和v5此时不属于同一个集合即v2和v5不连通，所以把v2和v5连起来，把v2和v5归并为同一个集合：

如下图，接下来进行第三轮的处理，权值为3的边的两头为v1和v4，v1和v4此时不属于同一个集合即v1和v4不连通，所以把v1和v4连起来，把v1和v4归并为同一个集合：

如下图，接下来进行第四轮的处理，其中一条权值为4的边的两头为v2和v3，v2和v3此时不属于同一个集合即v2和v3不连通，所以把v2和v3连起来，把v2和v3归并为同一个集合：

如下图，接下来进行第五轮的处理，其中一条权值为4的边的两头为v3和v5，v3和v5此时属于同一个集合即v3和v5连通，所以v3和v5之间的边会跳过，不选中：

接下来的过程同理，最终把v1与v3连接后就得出最小生成树，

如下图，总之就是要把所有的边都遍历一遍，每当处理一条边时，需要判断这条边所连接的两个顶点是否从属于同一个集合，如果不是，那就把这条边选中，如果是，就不选中：

2.时间复杂度分析：

假设图中共有e条边：

每轮循环中判断两个顶点是否属于同一个集合，要用到并查集，这个过程的时间复杂度详情见"5.15.并查集"，共e轮。

---

八.总结：

---