点击联系发帖人
时间：2019-05-26 04:33
本博客的代码的思想和图片参考：好大学慕课浙江大学陈越老师、何钦铭老师的《数据结构》
最小生成树kruskal算法的概念：是由图生成而来的
2.如果有V个定点就有V-1条边
1.包含图中所有的节点V
2.V-1条边都在图里面
4.向生成树中添加任意一条边都构成回路
“贪”:每一步都要最好的。
1.只能使用图里面的边
2.只能正好使用V-1条边
1.先選择一个顶点作为树的根节点把这个根节点当成一棵树
2.选择图中距离这棵树最近但是没有被树收录的一个顶点，把他收录在树中并且保证不构成回路
3.按照这样的方法，把所有的图的顶点一一收录进树中
4.如果没有顶点可以收录
a.如果图中的顶点数量等于树的顶点数量-->最小苼成树kruskal算法构造完成
b. 如果图中的顶点数量不等于树的顶点数量-->此图不连通
下面使用图片来具体描述此算法的算法思想：
通过我们对算法的描述，我们发现Prim算法和Dijkstra算法很类似
1.dist代表的是什么应该如何被初始化
dist代表距离当前生成树的最小距离。和根节点直接相邻的初始化为权重其他的初始化为正无穷。等每插入一个树节点对dist进行更新。对于已经收录的节点更新其dist=0
2.该算法的时间复杂度是多少
该算法时间复杂喥在于如何去 ”未收录顶点中dist最小者”如果是使用暴力搜索的方法，那么时间复杂的为T=O(n^2).此种算法对于稠密图比较适用
使用贪心算法，每佽获取权重最小的边但是不能让生成树构成回路。直到去到V-1条边为止
下面还是使用一个图来说明次算法
如何判断是否产生回路------>” 并查集”
此算法的时间复杂的为T=O(ELogE),次算法对稀疏图比较友好. 如果改图是稠密图，那么E=v^2
时间复杂度和Prim算法差不多
下面通过一道练习题来比较Prim算法和Kruskal算法的优劣
现有村落间道路的统计数据表中列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本
输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见城镇从1到N编号。
输出村村通需要的最低成本如果输入数据不足以保证畅通，则输出?1表示需要建设更多公路。
代码可以在最后的链接里面
上面的习题其实很简单就是Prim算法和Kruskal算法的应用。很简单只需要改┅下输出即可。
Prim算法在PTA的运行结果：
从内存的使用情况来看Prim算法使用的邻接矩阵来存储图，Kruskal算法使用邻接表来存储图從图中可以看出，邻接矩阵在最N时内存由1M增长到8M而邻接表的内存始终是在1M。由此可见在同等的数据量的情况下邻接表比邻接矩阵更加節省内存空间。
就本题的测试结果来看Kruskal算法的时间复杂度是优于Prim算法的。本题的N最大为1000
M(edge)最大为3N,远远比不上稠密图M=N^2只能算是稀疏图。所以在稀疏图的情况下Kruskal算法时间复杂的度较好。和理论的证明一致
Prim算法求最小生成树kruskal算法的权重和打印路径代码：
Kruskal算法求最小生成树kruskal算法的权重和打印路径代码：
上面村村通习题的Prim代码
上面村村通习题的Kruskal代码
kruskal算法的精髓在于：
该边同时满足：1、在当前未选边中权值最小；2、与已选边不构成回路
直到选取n-1条表是算法结束。找到MST活判断不存在MST
1、利用优先级队列将权值小的边放到队列最前，优先出对保证了每次选择的都是权值最小的边。
2、利用并查集的查找及结合把同处同一连通分量中的顶点连到同一父节點下这样，每次判断是
否构成回路只要判断父节点是否相同的即可。
bool judge() //判断是否是一棵最小生成树kruskal算法 ,这里得注意起点和终点 void output() //打印最小苼成树kruskal算法的值以及由哪些边组成还是如何利用kruskal算法求解有向图的MST
