图的最小生成树算法

在上一篇文章中，我们看了一下图的遍历算法，主要是对图的深度优先遍历和图的广度优先遍历算法思想的介绍。接下来让我们来看一下图的最小声成树算法。

首先，我们要知道，图的最小生成树是针对于有权图而言的，笔者的上一篇文章只介绍了无权图，其实有权图和无权图唯一的区别就是有权图的边是有权值的，不同的边权值可以不同，对于无权图我们可以把它看成所有边的权值都相等的有权图。好了，下面我们来看一个有权图：

这是百度百科上的一张有权图的图片，和无权图相比多了边的权值。Ok，那么最小生成树算法是什么呢？其实就是我们从给定的无向图中构造出一个无向且无回路子图（图的顶点不能减少），使得图的任意两个顶点都能通过若干条边直接或者间接连同，当构造的子图的边的权值之和最小的时候，这个子图就是这个图的最小生成树。

求最小生成树的算法主要有两种：克鲁斯卡尔（Kruskal）算法和普里姆（Prim）算法。下面一一介绍这两种算法：

Kruskal 算法的思想，简单来说，就是如果一个图有 n 个顶点，选出总权值最小并且不会构成回路的 n-1 条边使得图中的任意两个顶点都能通过这 n-1 条边中的若干条边连通。
这里可能有些小伙伴要问了，为什么选择 n-1 条边就能使得图的任意两个顶点连通？因为在图中的两个顶点之间如果没有回路的话最多相隔 n-1 条边，不信的话你可以画几个图看看（注意这里说的是没有回路的图）。

对于 Kruskal 算法的实现，既然要选择选择 n-1 条边并且边的总权值最小，那么我们可以先对这个图的所有边按权值进行从小到大排序，然后依次选择边。在 Kruskal 算法中一个比较麻烦的就是如何判断当前选择的边会不会和已经选择的边产生回路，这里我们可以运用查并集的思想（对查并集不了解的小伙伴可以看一下这篇文章http://blog.csdn.net/hacker_zhidian/article/details/60965556）。
我们我们将已经选择了的边的顶点看做一个集合（它们有共同的祖先），对于没有加入生成树的顶点将它们每个顶点单独看成一个集合。那么我们选择边的时候只需要判断边的两个顶点是不是在同一个集合中，如果不在同一个集合中，那么这条边和已经加入生成树的边就不会产生回路，就可以选择这条边，否则的话就不能加入生成树中。重复这个过程，直到选择了 n-1 条边。
以上面那个无向图为例，我们来模拟一下最小生成树的构造过程：

这是笔者在纸上模拟的过程，到最后，生成的最小生成树的权值之和为 15 。

下面我们来看一下 Prim 算法的核心思想：
我们换个角度思考一下：既然最后我们需要的最小生成树一定要有 n 个顶点，那么我们直接向这个最小生成树加入图的顶点就行了。每次向生成树中加入距生成树的距离最小并且还未被加入生成树的顶点，同时通过这个加入的点对其他还未加入生成树的点进行松弛，缩小其他顶点到生成树的距离，重复这个过程，直到 n 个顶点都加入了生成树中。

Prim算法不需要用到查并集的思想，它使用的是 Dijkstra 单源最短路径的思想，只不过我