最小生成树算法讲解实用教案.pptx

会计学
1
最小生成(shēnɡ chénɡ)树算法讲解
第一页，共32页。
生成(shēnɡ chénɡ)树的概念
生成树
一个连通图的生成树是一个极小连通子图，它含有图中全部顶点(dǐngdiǎn)，但只有足以构成一棵树的n-1条边。
生成树不唯一
V3
V2
V4
V1
V6
V5
V3
V2
V4
V1
V6
V5
V3
V2
V4
V1
V6
V5
V3
V2
V4
V1
V6
V5
生成(shēnɡ chénɡ)树
第1页/共32页
第二页，共32页。
最小代价(dàijià)生成树
生成(shēnɡ chénɡ)树的代价等于其边上的权值之和。
V4
V1
V3
V2
V6
V5
6
5
1
2
6
6
5
5
3
4
V4
V1
V3
V2
V6
V5
6
1
6
5
4
V4
V1
V3
V2
V6
V5
1
2
5
3
4
第2页/共32页
第三页，共32页。
最小代价(dàijià)生成树
两种常用的构造最小生成(shēnɡ chénɡ)树的方法：
普里姆算法
克鲁斯卡尔算法
第3页/共32页
第四页，共32页。
假设N=(V，E)是连通网，TE是N上最小生成树中边的集合。
算法从U={u0}(u0∈V)，TE={}开始，重复执行下述操作：
在所有u∈U，v∈V-U的边(u，v)中找一条(yī tiáo)代价最小的边(u0 ,v0),将其并入集合TE，同时将v0并入U集合。
当U=V则结束，此时TE中必有n-1条边，则T=(V，{TE})为N的最小生成树。
普里姆算法构造最小生成树的过程是从一个顶点U={u0}作初态，不断寻找与U中顶点相邻且代价最小的边的另一个顶点，扩充到U集合直至U=V为止。
普里姆(Prim)算法(suàn fǎ)
第4页/共32页
第五页，共32页。
V4
V1
V3
V2
V6
V5
6
5
1
2
6
6
5
5
3
4
V4
V1
V3
V2
V6
V5
1
2
5
3
4
U
V-U
｛V1 ｝
｛ V2 ,V3 ,V4 , V5 ,V6 ｝
步骤(bùzhòu)
(0)
｛V1 ,V3 ｝
｛ V2 ,V4 , V5 ,V6 ｝
(1)
｛V1 ,V3 ,V6 ｝
｛ V2 ,V4 , V5 ｝
(2)
｛V1 ,V3 ,V6 ,V4 ｝
｛ V2, V5 ｝
(3)
｛V1 ,V3 ,V6 ,V4 ,V2 ｝
｛ V5 ｝
(4)
｛V1 ,V3 ,V6 ,V4 ,V2 ,V5 ｝
｛ ｝
(5)
最小代价(dàijià)生成树
普里姆算法求最小生成树：从生成树中只有一个顶点开始(kāishǐ)，到顶点全部进入生成树为止
第5页/共32页
第六页，共32页。
V4
V1
V3
V2
V6
V5
1
6
5
V1
V3
1
｛V1 ｝
｛ V2 ,V3 ,V4 , V5 ,V6 ｝
步骤(bùzhòu)
(0)
｛V1 ,V3 ｝
｛ V2 ,V4 , V5 ,V6 ｝
(1)
U
V-U
普里姆算法(suàn fǎ)求最小生成树：从生成树中只有一个顶点开始，到顶点全部进入生成树为止
最小代价(dàijià)生成树
第6页/共32页
第七页，共32页。
V4
V1
V3
V2
V6
V5
6
5
V1
V3
1
｛V1 ｝
｛ V2 ,V3 ,V4 , V5 ,V6 ｝
步骤(bùzhòu)
(0)
｛V1 ,V3 ｝
｛ V2 ,V4 , V5 ,V6 ｝
(1)
V6
｛V1 ,V3 ,V6 ｝
｛ V2 ,V4 , V5 ｝
(2)
4
6
5
5
4
U
V-U
普里姆算法求最小生成(shēnɡ chénɡ)树：从生成(shēnɡ chénɡ)树中只有一个顶点开始，到顶点全部进入生成(shēnɡ chénɡ)树为止
最小代价(dàijià)生成树
第7页/共32页
第八页，共32页。
V4
V1
V3
V2
V6
V5