精品数据结构图.PPT

1、 数据结构数据结构第七章第七章(上上)数据结构数据结构tjm7.1 7.1 图的定义和术语图的定义和术语7.2 7.2 图的存储结构图的存储结构 7.2.1 7.2.1 数组表示法数组表示法 7.2.2 7.2.2 邻接表邻接表7.3 7.3 图的遍历图的遍历 7.3.1 7.3.1 深度优先搜索深度优先搜索 7.3.2 7.3.2 广度优先搜索广度优先搜索7.4 7.4 图的连通性问题图的连通性问题 7.4.3 7.4.3 最小生成树最小生成树7.5 7.5 有向无环图及其应用有向无环图及其应用 7.5.1 7.5.1 拓扑排序拓扑排序7.6 7.6 最短路径最短路径 7.6.1 7.6.1

2、 从某个源点到其余各顶点的最短路径从某个源点到其余各顶点的最短路径 7.6.2 7.6.2 每一对顶点之间的最短路径每一对顶点之间的最短路径数据结构数据结构tjm图的类型定义参见图的类型定义参见p156p156是一种多对多的结构关系，每个元素是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后可以有零个或多个直接前趋；零个或多个直接后继。图是由顶点集合继。图是由顶点集合(vertex)(vertex)及顶点间的关系集及顶点间的关系集合组成的一种数据结构：合组成的一种数据结构： graphgraph( v, r ) ( v, r ) 其中其中 v = v | v v = v

3、 | v 某个数据对象某个数据对象 是顶点的有穷非空集合；是顶点的有穷非空集合； r =vr=(v, w) | v, w r =vr=(v, w) | v, w v v 数据结构数据结构tjm在有向图中，顶点对在有向图中，顶点对是是有序的。在无向图中，顶点对有序的。在无向图中，顶点对(x, y)(x, y)是无序的。是无序的。5367214有向图有向图v=1,2,3,4,5,6,7v=1,2,3,4,5,6,7vr=,vr=,有向边又可称为有向边又可称为, vi,vj, 中中vivi称为称为或初始点，或初始点，vjvj称为称为或终端点。或终端点。数据结构数据结构tjm无向图无向图5367214

4、v=1,2,3,4,5,6,7v=1,2,3,4,5,6,7vr=(1,3),(3,4),(4,5),(1,2),(2,6),(2,7),vr=(1,3),(3,4),(4,5),(1,2),(2,6),(2,7),(6,7),(5,6),(1,5),(1,7) (6,7),(5,6),(1,5),(1,7) 数据结构数据结构tjm 若无向图中存在边若无向图中存在边(v, u)(v, u)，则称顶点，则称顶点v v和和u u互为邻接点；边互为邻接点；边(v, u)(v, u)依附于顶点依附于顶点v v和和u u；或者说边；或者说边(v, u)(v, u)和顶点和顶点v v和和u u相相关联。关

5、联。 在无向图中：在无向图中：顶点顶点v v的度的度 = = 与与v v相关联的边的数目相关联的边的数目 在有向图中：在有向图中： 顶点顶点v v的出度的出度= =以以v v为狐尾的有向边数为狐尾的有向边数 顶点顶点v v的入度的入度= =以以v v为狐头的有向边数为狐头的有向边数 顶点顶点v v的度的度= v= v的出度的出度+v+v的入度的入度 v0v0 v4v4 v3v3 v1v1 v2v2 v0v0 v1v1 v2v2 v3v3数据结构数据结构tjm 无向图无向图g =g =（v v，ee）中的顶点序列）中的顶点序列v v1 1,v,v2 2, , ,v ,vk k, ,若若(v(vi

6、 i,v,vi+1i+1) ) e( i=1,2,e( i=1,2,k-1), v =vk-1), v =v1 1, u =v, u =vk k, , 则则称该序列是从顶点称该序列是从顶点v v到顶点到顶点u u的路径。的路径。若若v=uv=u，则称该序列为回路。则称该序列为回路。在图在图g1g1中，中，v0,v1,v2,v3 v0,v1,v2,v3 是是v0v0到到v3v3的路径。的路径。 v0,v1,v2,v3,v0v0,v1,v2,v3,v0是回路。是回路。 v0v0 v4v4 v3v3 v1v1 v2v2例：例：数据结构数据结构tjm有向图有向图g2g2 v0v0 v1v1 v2v2

7、v3v3在图在图g2g2中，中，v0,v2,v3 v0,v2,v3 是是v0v0到到v3v3的路径。的路径。v0,v2,v3,v0v0,v2,v3,v0是回路。是回路。有向图有向图g =g =（v v，ee）中的顶点序列）中的顶点序列v v1 1,v,v2 2, , ,v ,vk k, , 若若 e (i=1,2,e (i=1,2,k-1), v =vk-1), v =v1 1, u =v, u =vk k, , 则则称该序列是从顶点称该序列是从顶点v v到顶点到顶点u u的路径。的路径。若若v=uv=u，则称该序列为回路。则称该序列为回路。例：例：数据结构数据结构tjm 在一条路径中在一条路

8、径中, ,若除起点和终点外若除起点和终点外, ,所有顶点各不所有顶点各不相同相同, ,则称该路径为简单路径。则称该路径为简单路径。 由简单路径组成的回路称为简单回路。由简单路径组成的回路称为简单回路。 在图在图g1g1中，中，v0,v1,v2,v3 v0,v1,v2,v3 是简单路径。是简单路径。 v0,v1,v2,v4,v1v0,v1,v2,v4,v1不是简单路径。不是简单路径。在图在图g2g2中，中， v0,v2,v3,v0v0,v2,v3,v0是简单回路。是简单回路。无向图无向图g1g1有向图有向图g2g2 v0v0 v4v4 v3v3 v1v1 v2v2 v0v0 v1v1 v2v2

9、v3v3数据结构数据结构tjm 非连通图非连通图 连通图连通图 强连通图强连通图 非强连通图非强连通图 v0v0 v1v1 v2v2 v3v3 v0v0 v4v4 v3v3 v1v1 v2v2 v0v0 v1v1 v2v2 v3v3 v0v0 v2v2 v3v3 v1v1 v5v5 v4v4在无（有）向图在无（有）向图g=( v, e )g=( v, e )中，若对任何两个顶中，若对任何两个顶点点 v v、u u 都存在从都存在从v v 到到 u u 的路径，则称的路径，则称g g是连通图是连通图（强连通图）。（强连通图）。数据结构数据结构tjm(a)(a)(b)(b)(c)(c) v0v0

10、v4v4 v3v3 v1v1 v2v2 v0v0 v4v4 v3v3 v1v1 v2v2 v0v0 v4v4 v3v3 v1v1 v2v2设有两个图设有两个图g=g=（v v，ee）、）、g1=g1=（v1v1，e1e1），），若若v1v1 v v，e1 e1 e e，则称，则称 g1g1是是g g的子图。的子图。例例:(b):(b)、(c) (c) 是是 (a) (a) 的子图的子图某些图的边具有与它相关的数某些图的边具有与它相关的数, , 称之为权。称之为权。这种带权图叫做网络。这种带权图叫做网络。数据结构数据结构tjm非连通图非连通图 v0v0 v2v2 v3v3 v1v1 v5v5 v

11、4v4无向图无向图g g 的极大连通子图称为的极大连通子图称为g g的连通分量。的连通分量。极大连通子图意思是：该子图是极大连通子图意思是：该子图是 g g 连通子图，将连通子图，将g g 的任何不在该子图中的顶点加入，子图不再连通。的任何不在该子图中的顶点加入，子图不再连通。 v0v0 v2v2 v3v3 v1v1 v5v5 v4v4连通分量连通分量数据结构数据结构tjm有向图有向图g g 的极大强连通子图称为的极大强连通子图称为g g的强连通分量。的强连通分量。极大强连通子图意思是：该子图是极大强连通子图意思是：该子图是g g的强连通子图的强连通子图，将，将d d的任何不在该子图中的顶点加

12、入，子图不再的任何不在该子图中的顶点加入，子图不再是强连通的。是强连通的。强连通分量强连通分量 v0v0 v1v1 v2v2 v3v3 v0v0 v2v2 v3v3 v1v1图中边或弧所具有的相关数称为权。表明从图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。一个顶点到另一个顶点的距离或耗费。带权带权的图称为的图称为。数据结构数据结构tjm：该子图是：该子图是g g 的连通子图，在该子的连通子图，在该子图中删除任何一条边，子图不再连通。图中删除任何一条边，子图不再连通。包含无向图包含无向图g g 所有顶点的极小连通子图称为所有顶点的极小连通子图称为g g 的的生成树。对

13、非连通图，则称由各个连通分量的生生成树。对非连通图，则称由各个连通分量的生成树的集合为非连通图的生成森林。成树的集合为非连通图的生成森林。 连通图连通图 g1g1g1g1的生成树的生成树 v0v0 v4v4 v3v3 v1v1 v2v2 v0v0 v4v4 v3v3 v1v1 v2v2 v0v0 v4v4 v3v3 v1v1 v2v2数据结构数据结构tjm，其它或若0ev,v)v,(v1,jijijia例：例：g124130001100000000110表示顶点间相联关系的矩阵。表示顶点间相联关系的矩阵。定义：设定义：设g=(v,e)g=(v,e)是有是有n n 1 1个顶点的图，个顶点的图，

14、g g的邻接的邻接矩阵矩阵a a是具有以下性质的是具有以下性质的n n阶方阵阶方阵：数据结构数据结构tjm例：例：15324g20011000101110101010101010，其它或若ev,v)v,(v,jijiijjia网的邻接矩网的邻接矩阵可定义为：阵可定义为：6183624127845375例：例：1452375318642数据结构数据结构tjm 数据结构数据结构tjmadjvex nextarcvexdata firstarc实现：为图中每个顶点建立一个单链表，第实现：为图中每个顶点建立一个单链表，第i i个单个单链表中的结点表示依附于顶点链表中的结点表示依附于顶点v vi i的边（有向图中指的边（有向图中指以以v vi i为尾的弧）。为尾的弧）。例：例：g1bdac1234acdbvexdatafirstarc 3 2 4 1