22问答网
所有问题
最小生成树的两种算法?
图的最小生成树的两个主要算法是什么?它们各自的特点?
举报该问题
推荐答案 2007-05-22
主要有两个:
1.普里姆(Prim)算法
特点:时间复杂度为O(n2).适合于求边稠密的最小生成树。
2.克鲁斯卡尔(Kruskal)算法
特点:时间复杂度为O(eloge)(e为网中边数),适合于求稀疏的网的最小生成树。
温馨提示:答案为网友推荐,仅供参考
当前网址:
http://22.wendadaohang.com/zd/fXSSSh0S.html
其他回答
第1个回答 2007-05-22
Prim算法 和 Kruskal算法
Prim算法逐次将最小权的边和相应顶点加到集合中,适合于求边稠密的最小生成树;Kruskal算法先将所有边都放入集合,然后再逐个选择最小权的边,适合于求稀疏的网的最小生成树。
详细过程请参考相关资料
第2个回答 2007-05-22
Prim算法
Kruskal算法
相似回答
求离散数学中的
最小生成树的
问题。
答:
离散数学中求最小生成树的方法有Prim算法和Kruskal算法
。Prim算法:1. 从图中任意选择一个顶点作为起始顶点,将其加入到最小生成树中;2. 在未被加入最小生成树的顶点中,找出一条权值最小的边,将该边的另一个顶点加入到最小生成树中;3. 重复步骤2,直到最小生成树中包含了所有的顶点。Kruskal...
直观理解:
最小生成树算法
Prime和Kruskal
答:
解释完上述名词之和,
接下来我们重点介绍两种经典的最小生成树算法Prime算法和Kruskal算法
。 假设存在联通图 ,图中所有的顶点集合为 ,集合 表示已经加入到生成树中的顶点集合,集合 表示未加入到生成树中的顶点集合。一开始,随机指定一个顶点 加入到集合 中,则 ,每次从集合...
大家正在搜
两种生成最小生成树的方法
图的最小生成树有两种算法
最小生成树两种算法的区别
最小生成树两种算法的优缺点
最小生成树的两个算法是什么
最小生成树问题的算法
最小生成树与最邻近算法
kruskal算法求最小生成树
最小生成树算法例题
相关问题
最小生成树的两种算法? 图的最小生成树的两个主要算法是什么?...
最小生成树两种算法有何区别
最小生成树算法,急!
简答:试比较求网的最小生成树的两个算法
最小生成树存在线性算法吗?
图的最小生成树算法?
最小生成树算法有哪些?应该有很多种~(除了Kruskal算法...
最小生成树的算法时间复杂度最小是多少?