PPT《《 数据结构》》

《 数据结构》

第七章 图(上)

第七章 图7.

1 图的定义和术语7.2 图的存储结构 7.2.1 数组表示法 7.2.2 邻接表7.3 图的遍历 7.3.1 深度优先搜索 7.3.2 广度优先搜索7.4 图的连通性问题 7.4.3 最小生成树7.5 有向无环图及其应用 7.5.1 拓扑排序7.6 最短路径 7.6.1 从某个源点到其余各顶点的最短路径 7.6.2 每一对顶点之间的最短路径 图的类型定义参见P156 7.1 图的定义和术语 图的定义:是一种多对多的结构关系,每个元素可以有零个或多个直接前趋;

零个或多个直接后继.图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构:Graph=( V, R ) 其中 V = { v | v ? 某个数据对象} 是顶点的有穷非空集合;

R ={VR}={(v, w) | v, w ? V } 基本术语: 有向图与无向图 在有向图中,顶点对是有序的.在无向图中,顶点对(x, y)是无序的.

5 3

6 7

2 1

4 有向图 V={1,2,3,4,5,6,7}VR={,,

,,

,,

,,

} 有向边又可称为弧, 中vi称为狐尾或初始点,vj称为狐头或终端点. 无向图

5 3

6 7

2 1

4 V={1,2,3,4,5,6,7}VR={(1,3),(3,4),(4,5),(1,2),(2,6),(2,7),(6,7),(5,6),(1,5),(1,7) } 邻接点及关联 若无向图中存在边(v, u),则称顶点v和u互为邻接点;

边(v, u)依附于顶点v和u;

或者说边(v, u)和顶点v和u相关联. 顶点的度、入度、出度在无向图中:顶点V的度 = 与V相关联的边的数目 在有向图中: 顶点V的出度=以V为狐尾的有向边数 顶点V的入度=以V为狐头的有向边数 顶点V的度= V的出度+V的入度 V0 V4 V3 V1 V2 V0 V1 V2 V3 路径、回路 无向图G =(V,{E})中的顶点序列v1,v2,… ,vk,若(vi,vi+1)?E( i=1,2,…k-1), v =v1, u =vk, 则称该序列是从顶点v到顶点u的路径.若v=u,则称该序列为回路. 在图G1中,V0,V1,V2,V3 是V0到V3的路径.V0,V1,V2,V3,V0是回路. V0 V4 V3 V1 V2 例: 有向图G2 V0 V1 V2 V3 在图G2中,V0,V2,V3 是V0到V3的路径.V0,V2,V3,V0是回路. 有向图G =(V,{E})中的顶点序列v1,v2,… ,vk, 若?E (i=1,2,…k-1), v =v1, u =vk, 则称该序列是从顶点v到顶点u的路径.若v=u,则称该序列为回路. 例: 在一条路径中,若除起点和终点外,所有顶点各不相同,则称该路径为简单路径. 由简单路径组成的回路称为简单回路. 在图G1中,V0,V1,V2,V3 是简单路径.V0,V1,V2,V4,V1不是简单路径.在图G2中, V0,V2,V3,V0是简单回路. 无向图G1 有向图G2 V0 V4 V3 V1 V2 V0 V1 V2 V3 简单路径和简单回路 非连通图 连通图 强连通图 非强连通图 V0 V1 V2 V3 V0 V4 V3 V1 V2 V0 V1 V2 V3 V0 V2 V3 V1 V5 V4 连通图(强连通图) 在无(有)向图G=( V, {E} )中,若对任何两个顶点 v、u 都存在从v 到u的路径,则称G是连通图(强连通图). (a) (b) (c) V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 子图 设有两个图G=(V,{E})、G1=(V1,{E1}),若V1? V,E1 ? E,则称 G1是G的子图.例:(b)、(c) 是(a) 的子图 权 某些图的边具有与它相关的数, 称之为权.这种带权图叫做网络. 连通分量(强连通分量) 非连通图 V0 V2 V3 V1 V5 V4 无向图G 的极大连通子图称为G的连通分量.极大连通子图意思是:该子图是 G 连通子图,将G 的任何不在该子图中的顶点加入,子图不再连通. V0 V2 V3 V1 V5 V4 连通分量 有向图G 的极大强连通子图称为G的强连通分量.极大强连通子图意思是:该子图是G的强连通子图,将D的任何不在该子图中的顶点加入,子图不再是强连通的. 强连通分量 V0 V1 V2 V3 V0 V2 V3 V1 权与网 图中边或弧所具有的相关数称为权.表明从一个顶点到另一个顶点的距离或耗费.带权的图称为网. 极小连通子图:该子图是G 的连通子图,在该子图中删除任何一条边,子图不再连通.包含无向图G 所有顶点的极小连通子图称为G 的生成树.对非连通图,则称由各个连通分量的生成树的集合为非连通图的生成森林. 连通图 G1 G1的生成树 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2 生成树和生成森林 图的几种基本操作参见P158. 例: G1