PDF《数据结构》

数据结构 孙猛 http://www.

math.pku.edu.cn/teachers/sunm sunmeng@math.pku.edu.cn 2015年12月3日 第十五讲 最小生成树 数据结构

2 v0 v1 v2 v8 v5 v6 v3 v7 v4

10 11

16 17

18 12

8 22

21 24

19 16

26 7

20 数据结构

3 v0 v1 v2 v8 v5 v6 v3 v7 v4

10 11

16 17

18 12

8 22

21 24

19 16

26 7

20 数据结构

4 v0 v1 v2 v8 v5 v6 v3 v7 v4

10 11

16 17

18 12

8 22

21 24

19 16

26 7

20 数据结构

5 v0 v1 v2 v8 v5 v6 v3 v7 v4

10 11

16 17

18 12

8 22

21 24

19 16

26 7

20 最小生成树 ? 对于连通的无向图或强连通的有向图,从任一顶 点出发周游,或是对于有根的有向图,从图的根 顶点出发周游,可以访问到图中所有的顶点. ? 周游时经过的边加上所有顶点构成了图的一个连 通子图,称为图的一棵生成树.

6 数据结构 生成树的构造 ? 周游可以按深度优先搜索,也可以按广度 优先搜索. ? 周游中记录访问到的所有顶点以及经过的 边,得到的分别是深度优先生成树或广度 优先生成树(简称为DFS生成树或BFS生成 树).

7 数据结构 例1 从无向图G的顶点??出发分别进行深度优先 周游和广度优先周游,得到的DFS及BFS生成 树如下图所示:

8 数据结构 ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? G DFS生成树 BFS生成树 例2 从有向图G的顶点v0出发周游,得到的DFS及BFS生 成树如图所示: V0 V0 V0 V1 V3 V4 V5 V1 V3 V4 V5 V1 V3 V4 V5 V2 V6 V2 V6 V2 V6 G DFS生成树 BFS生成树

9 数据结构 生成树林 ? 对于非连通的无向图和非强连通的有向图 ,从任一顶点出发通常不能访问到图中所 有的顶点,周游结果通常只能得到由各连 通分量的生成树或者各个有根子图的生成 树所组成的生成树林.

10 数据结构 最小生成树 ? 图的生成树不唯一,从不同顶点出发,或 从同一顶点出发,周游的路径不一样,则 得到的生成树都可能不同. ? 网络的生成树中的边也带权,将生成树各 边的权值加起来称为生成树的权,把权值 最小的生成树称为最小生成树(Minimum Spanning Tree,简称为MST).

11 数据结构 MST性质 U V - U 图GMST性质的证明: 对G的任一最小生成树 T,其中 必有一条一端在U另一端在V-U的边e'

.加上e得到一个包含环路的 图,去掉 e'

得到另一生成树,其 权不大于T 的权. e G = (V,E) 是网络,U是顶点集V的任一真子集. 假设有边 e = (u,v), 其顶点 u∈U, v∈V-U, 而且 e 是图 G 中所有一个端点在 U 另一端点在 V - U 里的边中权值最小的边, 则一定存在 G 的一棵包括边 e 的最小生成树. e'

12 数据结构 构造最小生成树的 prim 算法 ? 设? = (?, ?)是具有?个顶点的网络. ? ? = (?, ??)为(构造中)?的最小生成树, ?是?的顶点集合,??是?的边集合. ? 初始状态是空树. (1) 从集合?中任取一顶点(例如取顶点??)放入集合?中,这时 ? = {??},?? = ????, (2)在所有一个顶点在集合?里,另一个顶点在集合? ? ?里的 边中,找出权最小的边(?, ?)(? ∈ ?,? ∈ ? ? ?),将该边 放入??,并将顶点?加入集合?. 重复上述操作(2)直到? = ?为止. 结果??有? ? ?条边,? = (?, ??)就是?的一棵最小生成树.

13 数据结构 图及其关系矩阵

14 数据结构 v0

10 v1

21 11

5 v5

19 33

14 6 v2

6 v4

18 v3 v0

10 v1

21 11

5 v5

19 33

14 6 v2

6 v4

18 v3 v0

10 v1

21 11

5 v5

19 33