对下图,写出以普里姆算法,从顶点,1为起点,构建最小生成树的顶点序列和边的序列 @ prime1.jpg
时间: 2024-03-07 11:51:22 浏览: 142
最小生成树有很多种生成方法,主要有普利姆算法和克鲁斯卡尔算法
以普里姆算法构建最小生成树的顶点序列和边的序列如下:
顶点序列:1 - 2 - 4 - 5 - 3
边的序列:(1,2) - (2,4) - (4,5) - (2,3)
具体过程如下:
1. 从顶点1开始遍历,将1加入顶点序列中。
2. 以1为起点,遍历所有与1相邻的顶点,并将它们与1相连的边加入边集中。
3. 找出边集中权值最小的边(1,2),将顶点2加入顶点序列中。
4. 以顶点2为起点,遍历所有与2相邻的顶点,并将它们与2相连的边加入边集中。
5. 找出边集中权值最小的边(2,4),将顶点4加入顶点序列中。
6. 以顶点4为起点,遍历所有与4相邻的顶点,并将它们与4相连的边加入边集中。
7. 找出边集中权值最小的边(4,5),将顶点5加入顶点序列中。
8. 以顶点3为起点,遍历所有与3相邻的顶点,并将它们与3相连的边加入边集中。
9. 找出边集中权值最小的边(2,3),将顶点3加入顶点序列中。
10. 此时所有的顶点都在顶点序列中,最小生成树构建完成,边的序列为:(1,2) - (2,4) - (4,5) - (2,3)。
阅读全文