已知一个无向图如下，分别用普里姆和克鲁斯卡尔算法生成最小生成树（假设以1为起点，试画出构造过程）。
发布网友
发布时间：2022-04-26 18:20
共1个回答
热心网友
时间：2022-04-26 19:49
1)普里姆算法思想
从图中任意取出一个顶点， 把它当成棵树，然后从与这棵树相接的边中选取一条最短(权值最小)的边， 并将这条边及其所连接的顶点也并入这棵树中，此时得到了一棵有两个顶点的树。然后从与这棵树相接的边中选取一条最短的边，并将这条边及其所连顶点并入当前树中，得到一棵有3个顶点的树。以此类推，直到图中所有顶点都被并入树中为止，此时得到的生成树就是最小生成树。
2)克鲁斯卡尔算法思想
先将边中的权值从小到大排序，每次找出候选边中权值最小的边，就将该边并入生成树中。重复此过程直到所有边都被检测完为止。其中要注意的是克鲁斯卡尔算法需要用到并查集，以此来判断接下来要并入的边是否会和已并入的边构成回路。这两个图分别用普里姆和克鲁斯卡尔生成的最小生成树见图。
需要注意的是，在接下来要并入的最小权值不唯一的情况下，可以选取的边是不唯一的，所以其最小生成树也不唯一。(纯手打，望采纳，谢谢。)
