当前位置：文档之家 › 最小生成树算法详解ppt课件

最小生成树算法详解ppt课件

  • 格式：ppt
  • 大小：400.96 KB
  • 文档页数：35

下载文档原格式

  / 35

合集下载

02-13.2 最小生成树-PPT

02-13.2 最小生成树-PPT

本章小结
1 深刻理解基本回路、基本回路系统、基本割集、基本割集系统，并且对给定的生成树能 熟练地求出它们。
2 熟练地应用Kruskal算法求最小生成树。关于生成树的思维形式注记图如图所示。
W（TG）=1+3+4+8+9+23=48
算法13.3 （破圈法）
1）令E’=E; 2 选取E’中的一条简单回路C，设C 中权最大的边为e，令E’=E’-{e}； 3 重复步骤2），直到|E’|=|V|-1为止。 不停地选取图G 中的一条简单回路，从回路中删去权值最大的一条边，直 到图中无简单的回路为止。
1）按权值升序将图G 的边排序，得到表L；
2）令S=∅；
3 在表L中依次选取下一条边e，如果e ∉S ，且S ∪{e}构成的 子图是无圈图，则令S=S ∪{e}；
4 若|S|=n−1，则算法停止，输出集合S即为所求。否则，转3）， 继续遍历表L。 可以证明，算法13.1求得的是图G 的最小生成树。
例13.7
3 若|E(T)|=n−1，算法停止，输出E(T)。否则，转2），继续向树中增加新 结点。
例.8
右左图所示的赋权图G表 示七个城市a，b，c，d， e，f，g及架起城市间直 接通讯线路的预测造价。 试给出一个设计方案使 得各城市间能够通讯并 且总造价最小，并计算 出最小造价。
a
20
b
a
b
23
1
因为它们的加入会形成圈。
（4）此时S中有6条边，满足|S| =n - 1 ，所以算法结束。
得到的最小生成树如图（b）所示，树权为10。
算法13.2 （Prim算法）
设图G有n个结点，按以下步骤可以求得图G的最小生成树。

数据结构15--最小生成树PPT课件

数据结构15--最小生成树PPT课件

proc Union(i,j,c:longint); /*合并i和j所在集合 */
Var x,y:longint;
{ x←top(i); y←top(j); 点j所在子树的根*/
/*分别取出顶点i和顶
if x<>y Then { inc(ans,c);f[y]←x;}; /*若i 和j分属于两棵子树，则该边权计入最小生成树的权和， 两棵子树合并*/
Writeln(ans);
显然, Kruskal算法的效率取决于边数m,因此适用与
稀疏图。
.
②、Prim算法
集合A中的边总是只形成单棵树，每次添加到 树中的边都是使树的权尽可能小的边。
.
设 d[i]—顶点i与生成树相连的最短边长； ba[i]—顶点i在生成树的标志； w[i,j]—（i,j）的边长。若图中不存在边 （i,j），则w[i,j]=∞ min—所有未在生成树的顶点的最小距离 值
top←f[i]; /*返回顶点i所在并查集的代表 顶点*/ };/*top*/
.
通过过程Union(i,j,c)合并顶点i和顶点j所 在的两棵树
现有边权为c的边（i，j）。若该边的两个端点 分属于两棵树，顶点i和顶点j所在子树的根分别 为x和v，则(i,j) 加入最小生成树，合并两棵树 （即顶点i和顶点j所在的并查集）。
for j←1 to n do
if not ba[j]and(d[j]<min) then { k←j；min←d[j] }； /*then*/
if min= maxint then { ans←-1；break；}；/*若这样的顶点不存 在，则无解退出*/
ans←ans+min；ba[k]←true；/*最小距离值min计入生成树的权和, 顶点k进入生成树*/

信息学奥赛一本通 第4章 第6节 最小生成树(C++版) ppt课件

信息学奥赛一本通 第4章 第6节 最小生成树(C++版) ppt课件

5
71
4
min[3]=w[2][3]=1; min[5]=w[2][5]=2;
第三次循环是找到min[3]最小的蓝点3。将3变为白点，接着枚举与3相连的所有 蓝点4、5，修改它们与白点相连的最小边权。
1
2 4
22 16
5
3
7
1
4
min[4]=w[3][4]=1; 由于min[5]=2 < w[3][5]=6;所 以不修改min[5]的值。
2
1
2
12
8
10
9
5
6
3
1个集合{ {1，2，3，4，5} } 生成树中有4条边{ <1,2> ，<4,5>，<3，5>，<2,5>}
3
74
ppt课件
16
Kruskal算法
算法结束，最小生成树权值为19。 通过上面的模拟能够看到，Kruskal算法每次都选择一条最小的，且能合并两 个不同集合的边，一张n个点的图总共选取n-1次边。因为每次我们选的都是最小的 边，所以最后的生成树一定是最小生成树。每次我们选的边都能够合并两个集合， 最后n个点一定会合并成一个集合。通过这样的贪心策略，Kruskal算法就能得到一 棵有n-1条边，连接着n个点的最小生成树。 Kruskal算法的时间复杂度为O(E*logE)，E为边数。
第一行： 农场的个数，N（3<=N<=100）。
第二行..结 尾
后来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论 上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们 限制在80个字符，因此，某些行会紧接着另一些行。当然，对角 线将会是0，因为不会有线路从第i个农场到它本身。

最小生成树问题(共7张PPT)

最小生成树问题(共7张PPT)

个，所以支撑树是有不唯一]。
C n1 m
求最小树的Kruskal算法
赋权的连通图G=(V,E)中m=|E|,n=|V|,
S1:对E中各边的权排序，设 w1≤w2≤…≤wm,wi=w(ei)
S2:初始化： w←0,T←φ,k←1,t←0
S3:若t=n-1则转S6，否则转S4
Y
N
T’←T∪{ek}
T’成圈? N END
Y
T←T+ {ek},
k←k+1 w←w+wk,
t←t+1,k←k+1
用Kruskal算法求最小树
用Kruskal算法(避圈法)求赋权连通图G的最小树
V2
5
V6
Kruskal法盯住边,而Prim法更注意顶点:
T为最小树，w为T的权。
4
T={v1,v2,v3,v5}
Prim法求最小支撑树 E的权排序w1≤w2≤…≤wm w←0,T←φ,k←1,t←0
对要m让条程边序的读边懂长“图排”，序S程3，:序m如个何元判素断排是序否较成好“的圈算”？法谈是何基容于易分，治时策间略、的空快间速复排杂序性(Q绝u不ick应S小or看ting)，其时间复杂性是O(m㏒m)。
min S2:初始化：w←0,T←φ,k←1,t←0 设: {w(vv )}w(vv ) 简对称m条最边小的树边或长最排短序树，[管vvm线ij个 铺ST 元设素]。排序较好的i算法j是基于分治策略的快l速排k序(Quick Sorting)，其时间复杂性是O(m㏒m)。
S4:若T∪{ek}有圈则k←k+1转S4，否则 转S5
S5: T←T∪{ek},w←w+wk, t←t+1, k←k+1,转S3

图论课件--最小生成树37页PPT

图论课件--最小生成树37页PPT

9
6
63
2
7
2
10
3
4
3
1
用算法求出的生成路为：
9
6 3
2 2
1 12
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
直接在图中选出的一条生成路为：
6
63
2
3 1
后者的权值小于前者。
(二)、管梅谷的破圈法
在克鲁斯克尔算法基础上，我国著名数学家管梅谷 教授于1975年提出了最小生成树的破圈法。
解：过程如下：
1
v1
2
v5
v8
1 v5
v1
2
v8
1 v5
v1
2
3
1
v5
v8
5
v7
v4 v1
2
3
1
v5
v8
5
v7
v4 3 v8
v4
6
v3
8
1
0.5 n 0
0.5
1 2 1.5 t1
0.5
00
1 0.8
0.6 0.4 x 0.2
v1
v1
v4
2
v4 3
2
3
1
v5
v8
1
v5
v8
5
6
5
6
v6 8
v7
v6 8
图论课件--最小生成树
1、 舟 遥 遥 以 轻飏， 风飘飘 而吹衣 。 2、 秋 菊 有 佳 色，裛 露掇其 英。 3、 日 月 掷 人 去，有 志不获 骋。 4、 未 言 心 相 醉，不 再接杯 酒。 5、 黄 发 垂 髫 ，并怡 然自乐 。

算法设计与分析课件--贪心法-最小生成树问题

算法设计与分析课件--贪心法-最小生成树问题

6
4.5 最小生成树问题
◼ Prim算法思想：
❖Prim算法利用了最小生成树的上述性质。 ❖ 算法的关键是如何找出连接U和V-U所有边中的权值 最小的边(u, v)，并将v加入到U中。循环执行上述操作， 直至U=V为止。
7
4.5 最小生成树问题
◼ Prim算法设计：
❖ 设G=(V，E)是具有n个结点的无向连通带权图；设最 小生成树T=(U，TE)，算法结束时U=V，TE包含于E
点的无向连通带权图，U是
V的一个非空子集。最小生
成树的一个很重要的性质：
✓ (u, v)是一条具有最小权 值 的 边 ， 其 中 u∈U ， v∈V-U，则必存在一棵包
假设最小生成树T不包括(u,v)。 将(u,v)添加到T上产生回路， 将回路中另外一条边(u’,v’)去 掉得到另外一个树T’
含 边 (u ， v) 的 最 小 生 成 树 。
◼ Prim算法的求解示例：
18
4.5 最小生成树问题
◼ Prim算法的求解示例：
19
4.5 最小生成树问题
◼ Prim算法的求解示例：
20
4.5 最小生成树问题
◼ Prim算法的求解示例：
21
4.5 最小生成树问题
◼ Prim算法的求解示例：
22
4.5 最小生成树问题
◼ Prim算法的求解示例：
◼ Prim算法空间复杂性：
❖定义了辅助变量Q，其占用空间为|V|，从而空间复 杂度为O(|V|)。
27
4.5 最小生成树问题
◼ Prim算法的正确性证明：
❖最优子结构性质：假设最小生成树为T，从V-U集合中 添加到集合U中的结点顺序为< u0, …, ui, …, un-1, un>， 需要证明： 顺序< u0, …, ui, …, un-1>亦为图G’=(V\{un}， E\{e})最小生成树T’ ，其中e={原图G中与结点un相连 的边}。

最小生成树-数学建模.ppt

最小生成树-数学建模.ppt
用Kruskal算法可求出最小生成树，在前面 给出的Kruskal算法的MATLAB程序中，边权矩阵b 的值改为此处的边权矩阵，顶点数n改为9即可。
上一页 下一页 主 页
T= 7 8 15 12 39 46 47 45 13
c = 4.4300
机器的分组：{3， 9}，
{1，2，5}，
{4，6，7，8}。
返回
整理边权矩阵
初始化：j0, T, c0, k0； 对所有顶点i ,t(i)i .
B: 图的边权矩阵; T: 生成树的边集; C: 生成树的权; t: 顶点所属子树的编号
jj+1
t(B(1,j))t(B(2,j)) Y
N
TT(B(1,j),B(2,j)), cc+B(3,j),kk+1，i 0
i i+1
引例：计算机网络的线路设计
最小生成树
最大生成树 1) 一个完全图Kn有多少不同 的生成树？ 2) 如何求其最小生成树?
引例：计算机网络的线路设计
10个顶点的完全图，其不同的生成树就有 一亿棵。
一般地，n个顶点的完全图，其不同的生成 树个数为nn-2。
30 个 顶 点 的 完 全 图 就 有 3028 个 生 成 树 ， 求 最小生成树时用穷举法是无效的。
假设有13种零件，需在9台机器上 加工。在各台机器上加工的零件号在下 表中给出。
范例：制造系统的分组技术
机器 1 2 3 4 5 6 7 8 9
加工 2,3, 2,7, 1,6 3, 3,7, 5 4, 4, 6
的零 7,8, 8, 件 9, 11,1
12, 2
5, 8,9, 10 12,
13
10 10
3

最小生成树算法详解

最小生成树算法详解

Kruskal算法的核心是使用并查集来维护连通性，当一条边的两个顶点属于不同的 连通分量时，将这条边加入到生成树中，同时将两个连通分量合并为一个连通分 量，直到所有的连通分量都被合并为一个连通分量，生成树构建完毕。
算法步骤
初始化
将所有的边按照权值从小到大排序，初始化并查集和生成树。
选择边
从最小的边开始，依次选择每一条边，如果这条边的两个顶点属于不同的连通分量，将这 条边加入到生成树中，并将两个连通分量合并为一个连通分量。
最小生成树算法详解
xx年xx月xx日
目 录
• 最小生成树概述 • 普里姆算法（Prim算法） • 克鲁斯卡尔算法（Kruskal算法） • 最小生成树算法比较 • 最小生成树算法实践
01
最小生成树概述
定义与性质
定义
最小生成树是一个图的所有顶点连接起来形成的树，其所有 边的权重之和最小。
性质
最小生成树是一种最优树，它代表了从图中所有顶点中选择 一些顶点，使得这些顶点之间连接的边的权重之和最小。
重复选择
重复以上步骤，直到所有的边都被考虑过，生成树构建完毕。
Kruskal算法的拓展与优化
拓展
Kruskal算法适用于任何连通的带权图，不仅限于树和森林。
优化
在实现Kruskal算法时，可以通过优化查找和排序算法来提高效率。例如，使 用并查集的路径压缩和按秩合并优化来减少查找和合并操作的时间复杂度。
01
图论
最小生成树算法是图论中的一个经典问题，需要使用图的数据结构来
表示和解决问题。
02
并查集
并查集是一种用于处理不相交集合的数据结构，可以高效地解决最小
生成树算法中的连通性问题。
03

《数据结构MST》课件

《数据结构MST》课件

VS
最小生成树唯一性的证明
通过反证法，假设存在两棵不同的最小生 成树，它们之间至少存在一个边不同，那 么可以通过调整这条边来得到一棵权值和 更小的生成树，与最小生成树的定义矛盾 。
最小生成树性质
最小生成树的边数
01
在一个连通加权无向图中，最小生成树的边数等于顶点数减一
。
最小生成树的权值和
02
在一个连通加权无向图中，最小生成树的权值和等于所有边的
最小生成图问题
1 2 3
定义
给定一个带权重的连通图，寻找一种方式将该图 分解为若干个子图，使得所有子图的权值和最小 。
算法
可以采用Kruskal算法或Prim算法进行扩展，通 过将多个顶点划分为一个集合，然后寻找连接这 些集合的边，形成子图。
应用
在图像处理、化学分子结构分析等领域有广泛应 用，用于简化模型和提高计算效率。
电力系统网络优化
在电力系统中，最小生成树算法可以用于构 建低损耗的输电网络，提高电力传输效率。
最小生成树算法的实现步骤
选择起始节点
选择一个节点作为最小生成树 的根节点。
构建最小生成树
从根节点开始，按照权值从小 到大选择边，直到所有节点都 被连接起来。
构建无向图
将问题转化为无向图，并确定 所有节点和边。
要点二
克鲁斯卡尔算法（Kruskal's Algorithm）
按照边的权值从小到大排序，依次选择边，如果选择的边 不会与已选择的边构成环，则加入到生成树中，直到所有 顶点都连接在一起。
02
MST基本算法
Prim算法
总结词
Prim算法是一种求解最小生成树问题的贪心算法。
详细描述
Prim算法从图中的任意一个顶点开始，每次选择距离已选顶点集合最近的顶点 加入集合，直到所有顶点都被加入。该算法利用了贪心策略，每次选择局部最 优解，最终得到全局最优解。

最小生成树算法详解(课堂PPT)

最小生成树算法详解(课堂PPT)

0 0 0 0 0 {v1,v3,v6,v4,v2,v5}
{}
21
普里姆算法求最小生成树
• 图采用邻接矩阵表示
6 v2
5 3
6 v5
v1 5
1 v4 5
v3 42
6 v6
1
2
graph. arac[][] =
3 4
5
6
123456
∞ 6 1 5∞∞ 6 ∞5∞3 ∞ 1 5∞5 6 4 5 ∞ 5 ∞∞ 2 ∞ 3 6 ∞∞ 6 ∞∞4 2 6 ∞
6
adjvex lowcost
v3 5
0
v6 2
v3 6
0
{v1,v3,v6}
{v2,v4,v5 }
4
adjvex lowcost
v3 5
0
0
v3 6
0
{v1,v3,v6,v4}
{v2,v5 }
2
adjvex lowcost
0
0
0
v2 3
0
{v1,v3,v6,v4,v2}
{v5 }
5
adjvex lowcost
(5) ｛V1 ,V3 ,V6 ,V4 ,V2 ,V5 ｝ ｛ ｝
6
最小代价生成树
V1
1
普里姆算法求最小生成树：从
V3
生成树中只有一个顶点开始，
到顶点全部进入生成树为止
V1
6
5
1
V2
V4
V3
V5
V6
步骤 (0) (1)
U
V-U
｛V1 ｝ ｛ V2 ,V3 ,V4 , V5 ,V6 ｝ ｛V1 ,V3 ｝ ｛ V2 ,V4 , V5 ,V6 ｝

最小生成树PPT演示

最小生成树PPT演示

18
克鲁斯卡尔算法
• 克鲁斯卡尔算法从另一途径求网的最小生 成树。假设连通网N=(V,{E}),则令最小生成树 的初始状态为只有n个顶点而无边的非连通 图T=(V,{}),图中每个顶点自成一个连通分量 。在E中选择代价最小的边，若该边依附的 顶点落在T中不同的连通分量上，则将此边 加入到T中，否则舍去此边而选择下一条代 价最小的边。以此类推，直至T中所有顶点 都在同一连通分量上为止。
李昕翼： 撰写报告 提问问题
3
最小连接问题
• 交通网络中，常常关注能把所有站点连接 起来的生成树，使得该生成树各边权值之 和为最小。例如：
• 假设要在某地建造5个工厂，拟修筑道路连接这5 处。经勘探，其道路可按无向边铺设。现在每条 边的长度已经测出并标记在对应边上，如果我们 要求铺设的道路总长度最短，如何铺设？
10
V1
6
V2
5
1 5
V3
5
V4
3
V5
i
v2 closedge adjvex lowcost
V3 5 0
6 6
4
V6
v6
V3 4
2
v3
v4
V1 5
v5
V3 6
U
{V1, V3}
V-U
{V2,V4 ,V5,V6}
k
v6
11
V1
6
V2
5
1 5
V3
5
V4
3
V5
i
v2 closedge adjvex lowcost
V3 5
6 6
4
V6
v6
2
v3
v4
V6
v5
V3 6
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

(2) ｛V1 ,V3 ,V6 ｝ ｛ V2 ,V4 , V5 ｝
8
最小代价生成树
普里姆算法求最小生成树：从 生成树中只有一个顶点开始， 到顶点全部进入生成树为止
V1
1 V4
V3
42V6V165V2 5 V3
6
V5
6
5
V4
2 V6
步骤 U
V-U
(0) ｛V1 ｝ ｛ V2 ,V3 ,V4 , V5 ,V6 ｝
假设N=(V，E)是连通网，TE是N上最小生成树中边的集合。 算法从U={u0}(u0∈V)，TE={}开始，重复执行下述操作：
在所有u∈U，v∈V-U的边(u，v)中找一条代价最小的边(u0 ,v0),将 其并入集合TE，同时将v0并入U集合。
当U=V则结束，此时TE中必有n-1条边，则T=(V，{TE})为N的最小生 成树。
(4) ｛V1 ,V3 ,V6 ,V4 ,V2 ｝ ｛ V5 ｝
(5) ｛V1 ,V3 ,V6 ,V4 ,V2 ,V5 ｝ ｛ ｝
6
最小代价生成树
V1
1
普里姆算法求最小生成树：从
V3
生成树中只有一个顶点开始，
到顶点全部进入生成树为止
V1
6
5
1
V2
V4
V3
V5
V6
步骤 (0) (1)
U
V-U
｛V1 ｝ ｛ V2 ,V3 ,V4 , V5 ,V6 ｝ ｛V1 ,V3 ｝ ｛ V2 ,V4 , V5 ,V6 ｝
例如 下图的输出为
v1
6
5
v2
1 v4
55
v3
3 6
42
v5 6 v6
weight：15 (v1, v3) (v3, v6) (v6, v4) (v3, v2) (v2, v5) 或者(1, 3) (3, 6) (6, 4) (3, 2) (2, 5)
普里姆算法构造最小生成树的过程是从一个顶点U={u0}作初 态，不断寻找与U中顶点相邻且代价最小的边的另一个顶点， 扩充到U集合直至U=V为止。
5
最小代价生成树
普里姆算法求最小生成树：从 生成树中只有一个顶点开始， 到顶点全部进入生成树为止
V1
1
V2 5
V4
V3
3
4
2
V5
V6
6 V2 5
V1 5
(4) ｛V1 ,V3 ,V6 ,V4 ,V2 ｝ ｛ V5 ｝
(5) ｛V1 ,V3 ,V6 ,V4 ,V2 ,V5 ｝ ｛ ｝ 11
最小代价生成树
普里姆算法求最小生成树：从生 成树中只有一个顶点开始，到顶 点全部进入生成树为止
V1
1
V2 5
V4
V3
3
4
2
V5
V6
V1
V2 V3
步骤 U
V-U
V4
(1) ｛V1 ,V3 ｝ ｛ V2 ,V4 , V5 ,V6 ｝
(2) ｛V1 ,V3 ,V6 ｝ ｛ V2 ,V4 , V5 ｝
(3) ｛V1 ,V3 ,V6 ,V4 ｝ ｛ V2, V5 ｝
9
最小代价生成树
普里姆算法求最小生成树：从 生成树中只有一个顶点开始， 到顶点全部进入生成树为止
V1
1
V2 5
V4
V3
4
2
V6
V1 6
V2 5 V3
6
V5
6
V4 V6
步骤 U
V-U
(0) ｛V1 ｝ ｛ V2 ,V3 ,V4 , V5 ,V6 ｝
(1) ｛V1 ,V3 ｝ ｛ V2 ,V4 , V5 ,V6 ｝
(2) ｛V1 ,V3 ,V6 ｝ ｛ V2 ,V4 , V5 ｝
(3) ｛V1 ,V3 ,V6 ,V4 ｝ ｛ V2, V5 ｝
最小生成树算法
------prim& Kruskal
1
生成树的概念
生成树
➢ 一个连通图的生成树是一个极小连通子图，它含有图中全 部顶点，但只有足以构成一棵树的n-1条边。
➢ 生成树不唯一
V2
V2
V1
V4
V6 V5
V3 生成树
V1
V4
V6 V5
V2
V1
V4
V6 V5
V3
V2
V1
V4
V6 V5
V3
V3
普里姆(Prim)算法
开始
生成树中只放置一个顶点
生成树中顶点数小于n?否 是
在关联生成树顶点的边中（即边的 一个顶点在生成树中，另一个顶点不在） 取权值最小者
将选中的边加入生成树， 同时将该边的关联顶点加入生成树中
结束
13
基本要求
从键盘（或数据文件）输入图的信息，用普里姆算法求解给 定无向连通图的最小生成树，最后输出最小生成树中的权值 和所有的边，图的存储结构自行设定。
1
5
V4
V3
36
4
2
V5
6
V6
步骤 U
V-U
(0) ｛V1 ｝ ｛ V2 ,V3 ,V4 , V5 ,V6 ｝
(1) ｛V1 ,V3 ｝ ｛ V2 ,V4 , V5 ,V6 ｝
(2) ｛V1 ,V3 ,V6 ｝ ｛ V2 ,V4 , V5 ｝
(3) ｛V1 ,V3 ,V6 ,V4 ｝ ｛ V2, V5 ｝
(4) ｛V1 ,V3 ,V6 ,V4 ,V2 ｝ ｛ V5 ｝
10
最小代价生成树
普里姆算法求最小生成树：从生 成树中只有一个顶点开始，到顶 点全部进入生成树为止
V1
1
V2 5
V4
V3
3
4
2
V5
V6
V1
步骤 U
V-U
V2 V3
36
V5
6
V4 V6
(0) ｛V1 ｝ ｛ V2 ,V3 ,V4 , V5 ,V6 ｝ (1) ｛V1 ,V3 ｝ ｛ V2 ,V4 , V5 ,V6 ｝ (2) ｛V1 ,V3 ,V6 ｝ ｛ V2 ,V4 , V5 ｝ (3) ｛V1 ,V3 ,V6 ,V4 ｝ ｛ V2, V5 ｝
2
最小代价生成树
生成树的代价等于其边上的权值之和。
6 V2 5
V1 5
1
5
V4
V3
36
4
2
V1
6
5
V5
6
V6
V1
1
1
V2
V4
V3
V2 5
V4
V3
6
4
3
4
2
V5
V6
V5
V6
3
最小代价生成树
两种常用的构造最小生成树的方法： ➢ 普里姆算法（prim） ➢ 克鲁斯卡尔算法（ Kruskal）
4
普里姆(Prim)算法
(0)
｛V1 ｝ ｛ V2 ,V3 ,V4 , V5 ,V6 ｝
(1) ｛V1 ,V3 ｝ ｛ V2 ,V4 , V5 ,V6 ｝
V5
V6
(2) ｛V1 ,V3 ,V6 ｝ ｛ V2 ,V4 , V5 ｝ (3) ｛V1 ,V3 ,V6 ,V4 ｝ ｛ V2, V5 ｝ (4) ｛V1 ,V3 ,V6 ,V4 ,V2 ｝ ｛ V5 ｝ (5) ｛V1 ,V3 ,V6 ,V4 ,V2 ,V5 ｝ ｛ ｝ 12
7
最小代价生成树
普里姆算法求最小生成树：从 生成树中只有一个顶点开始， 到顶点全部进入生成树为止
V1 1 V3
4 V6
V1
6
5
V2 5
5
V4
V3
6
4
V5
V6
步骤 U
V-U
(0) ｛V1 ｝ ｛ V2 ,V3 ,V4 , V5 ,V6 ｝
(1) ｛V1 ,V3 ｝ ｛ V2 ,V4 , V5 ,V6 ｝