最小生成树
一个图的生成树是一个极小的连通子图，它含有图中全部的顶点，但只有足以构成一棵树的n-1条边。通俗一点讲，就是使用n-1条线把n个点连接起来，那么这些线和点构成的图形就叫生成树。在网图中，每条边有自己的权重，最小生成树就是指所有边的权重加起来最小的一种生成树。
最小生成树的典型应用如：要在一些村庄之间铺设电线，使所有的村庄都能通上电且成本最低（电线总长度最小），解决这个问题的过程就是求最小生成树。
克鲁斯卡尔(Kruskal)算法
1.1 算法原理
克鲁斯卡尔算法比较好理解，既然要保证总权重最小，就先把所有边按权重从小到大排列起来，然后依次取一条边回填至图中。因为要保证是生成树，所以不能有环路，如果回填某条边使得形成环路，则舍弃该边，继续选择下一条边回填，直到连接所有顶点。此时的生成树就是最小生成树。
可见，既然关注的是边的权重，采用边集数组的存储方式最方便。
边集数组
1.2 视频
视频描述的很形象，一看就懂。
视频：最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示
1.3 代码关键点
所以编程的关键是，如何判断是否形成环路？定义数组parent[]来判断边与边是否形成环路。
我们先看如何使用parent数组判断是否形成环路，再去讨论怎么生成更新这一数组。
在上图中，执行到i =6时，parent数组为
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| parent数组 | 1 | 5 | 8 | 7 | 7 | 8 | 0 | 0 | 6 |
其中，下标代表一条边所依附的一个顶点，对应parent元素代表改变所依附的另一个顶点，也就是说每列就是一条边。
由0→1→5→8→6和2→8说明v0、v1、v2、v5、v6、v8这六个点被连在了一起；由3→7和4→7说明v3、v4、v7在另一个集合里被连到了一起。
当新边edges[7]-5-6尝试回填时，其实就是判断v5和v6是否已经在一个集合里。
通过分析可知，当两个点在同一集合中时，将返回相同的数。
int Find(int *parent, int f)
{
while (parent[f] > 0)
f = parent[f];
return f;
}
如输入f = 0, 1, 5, 6, 8都将返回6，输入f = 3, 4, 7都将返回7。因此（5, 6）不能回填，继续尝试下一条边。
初始状态下，parent数组的值都为零，依次选择一条边回填时，判断是否形成环路，如果形成环路则舍弃改变继续尝试下一条边，如果不形成环路，则确认回填，并将改边写入parent数组。
这个思想还是比较有趣的，实际上parent数组通过<下标，元素>对应<起点，终点>，将相关联的点的集合串成了一串，通过Find函数，只要输入的点在这个集合中，最后总指向值为0的那个下标。
这个方法的巧妙之处在于将已加入生成树的顶点分成了两个集合，只有新加入的边的两个顶点在同一集合内才是形成了环路。只用一个selected数组是无法实现的。
1.4 代码
Graph/Kruskal_MiniSpanTree.c
普里姆(Prim)算法
2.1 基本原理
kruskal算法从边出发，采用依次尝试回填的方法找出最小生成树。而Prim算法则是从顶点出发，同样基于贪心算法的思想，依次找出局部最优，从而生成的最优方案也就是全局最优方案。
如下图所示，将已经归入最小生成树的顶点集合为左侧集合A，未归入的为右侧集合B。现在想继续寻找最小生成树的下一个顶点，就是在集合A、B分别找一个顶点，两顶点之间距离最小，将该B中的顶点归入最小生成树。这样不断寻找A集合与B集合之间的权值最小的边，直到所有顶点遍历完成。
具体过程同样参考前面的视频。
Prim算法示意图
2.2 关键代码
在编程中，是通过三个数组实现这一搜索过程的，分别是selected、minDist、parent。
selected数组初始化为0，表明还没有顶点加入生成树；
parent数组初始化为-1，用于标识每次新加入的边，同时方便打印结果。
选定一个初始顶点，这里选择V0，取出邻接矩阵的第0行对minDist数组进行更新，在这里更新后就是{0, 4, INF, INF, INF, INF, INF, 8, INF}，同时在parent数组对应的位置（下标分别是1和7的位置）写入父亲顶点（因为本次是扫描V0相连的顶点，所以写入0），在下一步就是找出权重最小的一条路径，将其加入最小生成树。在这里就是V1。
V1加入后，同样根据邻接矩阵，对minDist进行更新，现在可以看出minDist就是集合A与外围区域所有可能路径的权重，整个循环过程就是：
Update：更新minDist→Search：找出最小权重→Add：加入最小生成树
这样不断找出当前集合与外围集合之间权重最小的一条边加入生成树，最终将所有顶点遍历完毕后，得到的生成树就是最小生成树。
如果不使用selected数组也可以，这样需要将已完成顶点的信息保存在minDist数组中。
增加三个处理：
-
生成树每增加一个顶点，将对应下标的minDist值置为0（或者其他的一个特定值）标识该顶点已进入生成树。
选择0号顶点作为起点，也就是0进入生成树，那么此时minDist就是{0, INF, INF, INF, INF, INF, INF, INF, INF}。 -
使用G更新minDist时，不更新
minDist[i] == 0的顶点。因为如果为0，说明该顶点已经进入生成树。 - 扫描minDist得到最小权重时，排除0元素。
不过这样使代码逻辑不太清晰，还是增加一个selected[]数组好一点。
2.3 代码
Graph/Prim_MiniSpanTree.c
网友评论