已知图G如下所示,根据Prim算法,构造最小生成树。(要求给出生成过程)
N诺智能批改可自动批改答案并给出反馈,每次使用将消耗 1个诺币
您当前的诺币数量: 个
N诺正在智能批改,预计需要30秒,请稍候...
初始:生成树仅含 v0,候选边为 v0 关联边(v0-v1(8)、v0-v2(8)、v0-v4(6) )。 第 1 步:选最小边 v0-v4(6),生成树加入 v4,候选边更新(新增 v4 关联边:v4-v1(无直接边,原 v0 - v1 保留) 、v4-v3(无直接边)、v4-v5(4)、v4-v6(7) ,同时原候选边还在 )。 第 2 步:选最小边 v4-v5(4),生成树加入 v5,候选边更新(新增 v5 关联边 v5-v1(7)、v5-v7(8) )。 第 3 步:选最小边 v5-v1(7),生成树加入 v1,候选边更新(v1 无新关联边需补充,已有边继续参与)。 第 4 步:此时看候选边,选 v3-v6(2)(假设从与已有生成树顶点连通角度,比如 v6 相关,需结合整体,实际是找当前最小且能连接新顶点的边 ),生成树加入 v6,候选边更新(v6 关联边 v6-v2(2)、v6-v7(5) )。 第 5 步:选 v6-v2(2),生成树加入 v2,候选边更新(v2 关联边无新关键边 )。 第 6 步:选 v6-v3(2)(v3 相关,连接生成树 ),生成树加入 v3,候选边更新(v3 已加入 )。 第 7 步:选 v6-v7(5),生成树加入 v7 ,所有顶点加入生成树,过程结束。
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算法求最小生成树如下...
登录后提交答案