最小生成树是指在一个图中,由连接所有顶点的边构成的权值之和最小的树,求最小生成树的算法主要有Prim算法及Kruskal算法,此处介绍Prim算法的基本原理。
Prim算法是一种贪心算法,不过可以证明,此算法得到的必定是全局最优解。Prim算法的基本思路如下:
- 将图中的所有顶点分为两个集合,
Known
及Unknown
,初始时任意选择一个顶点放置在Known
中,其余顶点位于Unknown
中,算法的目标是将Unknown
中的所有顶点移至Known
中; - 选择一条边,这条边连接的两个顶点一个位于
Known
中,另一个位于Unknown
中,且这条边的权值是所有满足条件的边中最小的; - 将这条边添加到最小生成树中,并将其连接的那个位于
Unknown
集合中的顶点移至Known
中; - 重复以上两步,直至
Unknown
集合为空;
算法图示:
Prim算法的过程与Dijkstra算法很相像,故二者的程序结构也很类似。
在使用邻接表及二叉堆实现时,Prim算法的时间复杂度是 \(O(|E|log|V|)\),需要注意的是,无论对于稀疏图还是稠密图,这都是一个最优的算法复杂度。Kruskal算法的复杂度是 \(O(|E|log|E|)\),对于所有连通图来说都有 \(|E|>=|V|-1\),所以可以得出结论,Prim算法在时间复杂度上无论是对于稀疏图还是稠密图来说都是最优的,优于Kruskal算法。不过其最大缺点就是在使用二叉堆时空间复杂度会极大,对于超稠密图就很不合适了。具体定量比较可参考:
算法的实现代码有空再补上吧……
or 参考: 最小生成树的常用算法模板
标签:Prim,Unknown,复杂度,最小,生成,算法,Known,顶点 From: https://www.cnblogs.com/RioTian/p/16749468.html