有哪些信誉好的足球投注网站- 1、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。。
- 2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
查看更多
最小生成树生成算法
最小生成树的生成算法研究
班级：软件一班
姓名：徐政钧
学号：130120010002
定义：我们把构造连通网的最小代价生成树称为最小生成树。
普里姆（Prim）算法
克鲁斯卡尔（Kruskal）算法
最小生成树
go
go
27
12
4
8
26
10
48
17
15
普里姆（Prim）算法
v0 v1 v2 v3 v4 v5
v0
v1
v2
v3
v4
v5
adjvex
lowcost
K
27
12
4
8
26
10
48
17
15
v0
v1
v2
v3
v4
v5
0
0
0
0
0
0
adjvex
lowcost
K
v0 v1 v2 v3 v4 v5
min=65535
27
12
4
8
26
10
48
17
15
v0
v1
v2
v3
v4
v5
0
0
0
0
0
0
0
4
10
∞
∞
8
adjvex
lowcost
1
K
v0 v1 v2 v3 v4 v5
min=4
打印（0，1）
27
12
4
8
26
10
48
17
15
v0
v1
v2
v3
v4
v5
0
0
0
0
1
0
0
0
10
∞
12
8
adjvex
lowcost
1
5
K
v0 v1 v2 v3 v4 v5
min=8
打印（0，1）
打印（0，5）
27
12
4
8
26
10
48
17
15
v0
v1
v2
v3
v4
v5
0
0
0
5
1
0
0
0
10
27
12
0
adjvex
lowcost
1
2
5
K
v0 v1 v2 v3 v4 v5
min=10
打印（0，1）
打印（0，5）
打印（0，2）
27
12
4
8
26
10
48
17
15
v0
v1
v2
v3
v4
v5
0
0
0
2
1
0
0
0
0
17
12
0
adjvex
lowcost
1
2
4
5
K
v0 v1 v2 v3 v4 v5
min=12
打印（0，1）
打印（0，5）
打印（0，2）
打印（1，4）
27
12
4
8
26
10
48
17
15
v0
v1
v2
v3
v4
v5
0
0
0
2
1
0
0
0
0
17
0
0
adjvex
lowcost
1
2
3
4
5
K
v0 v1 v2 v3 v4 v5
min=17
打印（0，1）
打印（0，5）
打印（0，2）
打印（1，4）
打印（2，3）
back
27
12
4
8
26
10
48
17
15
克鲁斯卡尔（Kruskal）算法
begin
end
weight
Edges[0]
0
1
4
Edges[1]
0
5
8
Edges[2]
0
2
10
Edges[3]
1
4
12
Edges[4]
2
5
15
Edges[5]
2
3
17
Edges[6]
4
5
26
Edges[7]
3
5
27
Edges[8]
3
4
48
27
12
4
8
26
10
48
17
15
begin
end
weight
Edges[0]
0
1
4
Edges[1]
0
5
8
Edges[2]
0
2
10
Edges[3]
1
4
12
Edges[4]
2
5
15
Edges[5]
2
3
17
Edges[6]
4
5
26
Edges[7]
3
5
27
Edges[8]
3
4
48
Parent
判断是否产生回路
0
0
0
0
0
0
begin
end
weight
Edges[0]
0
1
4
Edges[1]
0
5
8
Edges[2]
0
2
10
Edges[3]
1
4
12
Edges[4]
2
5
15
Edges[5]
2
3
17
Edges[6]
4
5
26
Edges[7]
3
5
27
Edges[8]
3
4
48
Parent
1
0
0
0
0
0
n=0
m=1
4
打印：（0，1）
begin
end
weight
Edges[0]
0
1
4
Edges[1]
0
5
8
Edges[2]
0
2
10
Edges[3]
1
4
12
Edges[4]
2
5
15
Edges[5]
2
3
17
Edges[6]
4
5
26
Edges[7]
3
5
27
Edges[8]
3
4
48
Parent
1
0
0
0
0
0
n=1
m=5
4
打印：（0，1）
打印：（0，5）
8
begin
end
weight
Edges[0]
0
1
4
Edges[1]
0
5
8
Edges[2]
0
2
10
Edges[3]
文档评论（0）