最小生成树两种算法有何区别

发布网友发布时间：2022-05-02 04:01

共4个回答

热心网友时间：2022-06-28 00:27

主要有两个：
1.普里姆（Prim)算法

特点：时间复杂度为O(n2).适合于求边稠密的最小生成树。
2.克鲁斯卡尔（Kruskal)算法

特点：时间复杂度为O(eloge)(e为网中边数），适合于求稀疏的网的最小生成树。

热心网友时间：2022-06-28 00:28

http://www.sdfz.com.cn/Article/Print.asp?ArticleID=2140

热心网友时间：2022-06-28 00:28

Prim算法中寻找的是下一个与MST中任意顶点相距最近的顶点；
Dijkstra算法寻找的是下一个离给定顶点（单源）最近的顶点。
另外，当有两条具有同样的最小权值的边可供选择时，任选一条即可，所以构造的MST不是惟一的。
Prim算法和Dijkstra算法十分相似，惟一的区别是：
Prim算法要寻找的是离已加入顶点距离最近的顶点；
Dijkstra算法是寻找离固定顶点距离最近的顶点。
所以Prim算法的时间复杂度分析与Dijkstra算法相同，都是 O(|V^2|)

热心网友时间：2022-06-28 00:29