数据结构 - 南开大学.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