算法分析与设计实验报告 Project1

2021-06-09 03:02

阅读：580

问题
我们定义无向连通图的最小生成树为边权和最小的生成树
解析
求最小生成树通常有两种做法：
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

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：算法分析与设计实验报告 Project1
文章链接：http://soscw.com/index.php/essay/92488.html

亲，登录后才可以留言！