已知一个无向图如下图所示,要求分别用Prim和Kruskal算法生成最小树(假设以①为起点,试画出

p，树向外扩张，找最短外扩路径

k，增加一条不会造成回路的边(现在选中的边可以暂不相连)

按照prim是：（从起点到终点的边）

46，45，51，63，12，32

按照kruskal是：

46，15，45，63，12，32

克鲁斯卡尔算法思想先将边中的权值从小到大排序，每次找出候选边中权值最小的边，就将该边并入生成树中。重复此过程直到所有边都被检测完为止。

其中要注意的是克鲁斯卡尔算法需要用到并查集，以此来判断接下来要并入的边是否会和已并入的边构成回路。这两个图分别用普里姆和克鲁斯卡尔生成的最小生成树见图。

扩展资料：

无向图G=,其中：

1、V是非空集合，称为顶点集。

2、E是V中元素构成的无序二元组的集合，称为边集。

解释

直观来说，若一个图中每条边都是无方向的，则称为无向图。

无向边的表示

无向图中的边均是顶点的无序对，无序对通常用圆括号表示。

参考资料来源：百度百科-无向图