数据结构.-.南开大学.ppt

数据结构
第7章图- 2
第7章图
图的定义和术语
图的存储结构
图的遍历
图的连通性问题
有向无环图及其应用
最短路经
图的连通性问题
无向图的连同分量和生成树
有向图的强连同分量
最小生成树
关节点和重连同分量
无向图的连同分量和生成树
A
B
C
D
E
F
G
I
J
L
H
M
K
A
B
C
D
E
H
M
F
G
I
J
L
K
无向图G的三个连通分量
无向图G
连通:顶点v至v‘’之间有路径存在
连通图:无向图图 G 的任意两点之间都是连通的,则称 G 是连通图。
连通分量:极大连通子图
无向图的连同分量和生成树
生成树:极小连通子图。包含图的所有 n 个结点,但只含图的 n-1 条边。在生成树中添加一条边之后,必定会形成回路或环。因为在生成树的任意两点之间,本来就 是连通的,添加一条变之后,形成了这两点之间的第二条通路。
A
B
C
D
E
H
M
A
B
C
D
E
H
M
无向图G
无向图G的生成树
生成方法:进行深度为主的遍历或广度为主的遍历,得到深度优先生成树或广度优先生
成树。
生成森林:在进行深度为主的遍历或广度为主的遍历时,对于非连通图,将得到多棵深
度优先生成树或广度优先生成树。称之为生成森林。
无向图的连同分量和生成树
生成森林:在进行深度为主的遍历或广度为主的遍历时,对于非连通图,将得到多棵深
度优先生成树或广度优先生成树。称之为生成森林。
A
B
C
D
E
F
G
I
J
L
H
M
K
A
B
C
D
E
H
M
F
G
I
J
L
K
无向图G的生成森林
无向图G
有向图的强连同分量
深度优先搜索是求有向图的强连同分量的一个有效方法。
最小生成树
最小代价生成树(简称:最小生成树)
Minimum Cost Spanning Tree
定义:生成树中边的权值(代价)之和最小的树。
实例:
1
2
4
3
5
6
6
1
6
5
5
5
6
3
4
2
1
2
4
3
5
6
1
5
3
4
2
左图的最小代价生成树
MST 性质:
假设 G = {V, { E } } 是一个连通图,U 是结点集合 V 的一个非空子集。若( u, v ) 是
一条代价最小的边,且 u 属于 U , v 属于 V - U,则必存在一棵包括边( u, v ) 在内
的最小代价生成树。
最小生成树
证明:假定存在一棵不包括边( u, v ) 在内的最小代价生成树,设其为 T。将边( u, v )
添加到树 T ,则形成一条包含( u, v ) 的回路。因此,必定存在另一条边( u‘
,v‘) ,且 u’属于 U , v ‘属于 V - U。删去边( u‘,v‘) ,得到另一棵生成
树 T ‘; 因为边( u, v ) 的代价小于边( u‘,v‘) 的代价,所以新的生成树T ‘
将是代价最小的树。和原假设矛盾。
新的生成树T‘是树的理由:连通且无回路。
u
v
u’
v’
T
最小生成树
Kruscal 算法
1
2
4
3
5
6
6
1
6
5
5
5
6
3
4
2
最小代价生成树
1
2
4
3
5
6
1
5
3
4
2
5
5