算法分析与设计实验报告 Project1
2021-06-09 03:02
阅读：583
-
问题
我们定义无向连通图的最小生成树为边权和最小的生成树 -
解析
求最小生成树通常有两种做法：
1.Kruskal
将边权从小到大加边，若加边以后成环则放弃加边，直到加到n – 1条边，结束。(n为点集大小)加得到的边集就构成了一颗最小生成树。
2.Prime算法
用集合A,B分别表示得到的点集和未得到的点集，初始时刻A为空，B为所有点。
维护出A到B各个点的最小距离，每次将最小距离所在的边加入边集和对应的点加入A，移除B。重复上述步骤，直到B空，得到的边集就是要求的最小生成树。 -
设计
-
Kruskal
-
Prim
\ -
分析
n表示点数，m表示边数 -
Kruskal
如果我们选用O(mlogm)的排序算法，并且使用并查集优化判环，那么复杂度显然是
O(mlogm)。（α(m) -
Prim
每次用点来更新，用类似于最短路的方法把新加入的点松弛，如果我们使用堆优化来快速找出最短的边集，复杂度应当是O((n+m)logn)。（logn来自每次找到dis最小的点） -
源码
https://github.com/MQFLLY/Algorithm-Class-codes/blob/main/project1
下一篇：Python程序的流程
评论
亲，登录后才可以留言！