数据结构中关于最小生成树的步骤

答案:4 悬赏:50 手机版

解决时间 2021-04-27 20:26

提问者网友：爱了却不能说
2021-04-27 16:22

数据结构中关于最小生成树的步骤

最佳答案

五星知识达人网友：青尢
2021-04-27 18:00

普里姆算法的基本思想:取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。
克鲁斯卡尔算法
克鲁斯卡尔算法的基本思想：为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。
具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。

全部回答

1楼网友：独行浪子会拥风
2021-04-27 20:07

jrj

2楼网友：低血压的长颈鹿
2021-04-27 19:50

比较典型的是Prim算法和Kruskal算法。

我要举报

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息