已知一个无向网的顶点集V和边集E分别为:V={1,2,3,4,5,6,7}; E={(1,2,3),(1,3,5),(1,4,8),(2,5,10),(2,3,6),(3,4,15),(3,5,12),(3,6,9),(4,6,4),(4,7,20),(5,6,18),(6,7,25)},其中的三元组分别表示2个邻接顶点和权值,分别写出用Prim算法和Kruskal算法在构造最小生成树时依次得到的各条最小生成边。
时间: 2023-09-25 21:11:18 浏览: 166
使用Prim算法构造最小生成树的过程如下:
1. 任选一个起点,比如选择顶点1;
2. 找到与起点相邻的最小边,将其加入最小生成树中,这里是(1,2,3);
3. 接着找到与已经加入最小生成树的点相邻的最小边,将其加入最小生成树中,这里是(1,3,5);
4. 继续找到与已经加入最小生成树的点相邻的最小边,将其加入最小生成树中,这里是(3,6,9);
5. 重复步骤4,加入边(4,6,4)、(2,5,10)、(5,6,18)、(1,4,8);
6. 最后加入边(4,7,20),得到的最小生成树的边集为{(1,2,3),(1,3,5),(3,6,9),(4,6,4),(2,5,10),(5,6,18),(1,4,8),(4,7,20)}。
使用Kruskal算法构造最小生成树的过程如下:
1. 将所有边按照权值从小到大排序,得到的顺序为(4,6,4)、(1,2,3)、(1,4,8)、(3,6,9)、(2,3,6)、(5,6,18)、(3,5,12)、(1,3,5)、(4,7,20)、(2,5,10)、(6,7,25);
2. 从权值最小的边开始,判断该边的两个端点是否在同一连通块中,如果不在,则将该边加入最小生成树中,否则舍弃该边;
3. 重复步骤2,直到最小生成树的边数等于顶点数减一,得到的最小生成树的边集为{(4,6,4),(1,2,3),(1,3,5),(3,6,9),(2,5,10),(5,6,18),(4,7,20)}。
阅读全文