已知图G如下所示,根据Prim算法,构造最小生成树。(要求给出生成过程)
v0 v4
v0 v4 v5
v0 v4 v5 v1
v0 v4 v5 v1 v6
v0 v4 v5 v1 v6 v2
v0 v4 v5 v1 v6 v2 v3
v0 v4 v5 v1 v6 v2 v3 v7
111
1
0-4,
0-4,4-5
0-4,4-5,1-5
0-4,4-5,1-5,4-6
0-4,4-5,1-5,4-6,3-6
0-4,4-5,1-5,4-6,3-6,2-6
0-4,4-5,1-5,4-6,3-6,2-6,6-7
0-4,4-5,1-5,4-6,3-6,2-6,6-7,
0
04(0-4)
045(4-5)
0456(4-6)
04562(6-2)
045623(6-3)
0456237(6-7)
0456237(5-1)
这里4-6和5-1权值相同,在构造时能不能任选?
1.V6 --2-- v3
2.V2--2--V6
3.V6--5--V7
4.V6--7--V4
5.V4--5--V5
6.V4--6--V6
答案里面怎么没有v7?
admin 回复 Hyper_Vapor: 已更新
一共7步
1、v0
2、v0--6--v4
3、v0--6--v4--4--v5
4、v0--6--v4--4--v5--7--v1
5、v0--6--v4--4--v5--7--v1
|7
v6
6、v0--6--v4--4--v5--7--v1
v2--2--v6
7、v0--6--v4--4--v5--7--v1
v2--2--v6--2--v3
8、v0--6--v4--4--v5--7--v1
|5
v7
答案:prim算法求最小生成树如下...
用户登录可进行刷题及查看答案
答案:prim算法求最小生成树如下:
登录后提交答案