《数据结构》课程教学资源：电子教案 第9章 图

第9章图 9.1图的基本概念 9.2图的存储结构 9.3图的遍历 9.4生成树和最小生成树 9.5最短路径 9.6拓扑排序 9.7AOE网与关键路径 本章小结

9.1 图的基本概念 第9章 图 9.2 图的存储结构 9.3 图的遍历 9.4 生成树和最小生成树 9.5 最短路径 9.6 拓扑排序 本章小结 9.7 AOE网与关键路径

9.1图的基本概念 9.1.1图的定义 图( Graph)G由两个集合v( Vertex)和E(Edge)组成, 记为G=(V,E),其中V是顶点的有限集合记为VG,E是 连接中两个不同顶点(顶点对)的边的有限集合,记为 E(G 在图G中,如果代表边的顶点对是无序的则称G为 无向图无向图中代表边的无序顶点对通常用圆括号括 起来用以表示一条无向边。 如果表示边的顶点对是有序的则称G为有向图,在 有向图中代表边的顶点对通常用尖括号括起来

9.1 图的基本概念 9.1.1 图的定义 图(Graph)G由两个集合V(Vertex)和E(Edge)组成, 记为G=(V,E),其中V是顶点的有限集合,记为V(G),E是 连接V中两个不同顶点(顶点对)的边的有限集合,记为 E(G)。 在图G中,如果代表边的顶点对是无序的,则称G为 无向图,无向图中代表边的无序顶点对通常用圆括号括 起来,用以表示一条无向边。 如果表示边的顶点对是有序的,则称G为有向图,在 有向图中代表边的顶点对通常用尖括号括起来

9.1.2图的基本术语 1.端点和邻接点 在一个无向图中若存在一条边 (vpy则称v和v为此边的两个端点, 并称它们互为邻接点 在一个有向图中,若存在一条边 vpv>,则称此边是顶点v的一条出 边同时也是顶点v的一条入边;称 0 v和v分别为些边的起始端点(简称 为起点和终止端点(简称终点);称 v和v互为邻接点。 (b)

9.1.2 图的基本术语 1. 端点和邻接点 在一个无向图中,若存在一条边 (vi ,vj ),则称vi和vj为此边的两个端点, 并称它们互为邻接点。 在一个有向图中,若存在一条边 ,则称此边是顶点vi的一条出 边,同时也是顶点vj的一条入边；称 vi和vj分别为此边的起始端点(简称 为起点)和终止端点(简称终点)；称 vi和vj互为邻接点。 1 2 3 0 4 1 2 3 0 4 (a) (b)

2.顶点的度、入度和出度 在无向图中,顶点所具有的边 的数目称为该顶点的度。 在有向图中以顶点v为终点的 4 入边的数目,称为该顶点的入度 以顶点v为始点的出边的数目,称为 (a) 该顶点的出度。一个顶点的入度与 出度的和为该顶点的度。 若一个图中有n个顶点和e条边, 3 0 每个顶点的度为d1≤i≤n则有: 2 ∑

2. 顶点的度、入度和出度 在无向图中,顶点所具有的边 的数目称为该顶点的度。 在有向图中,以顶点vi为终点的 入边的数目,称为该顶点的入度。 以顶点vi为始点的出边的数目,称为 该顶点的出度。一个顶点的入度与 出度的和为该顶点的度。 若一个图中有n个顶点和e条边, 每个顶点的度为di (1≤i≤n),则有： 1 2 3 0 4 1 2 3 0 4 (a)  (b) = n i 1 di 2 1 e＝

3.完全图 若无向图中的每两个顶点之间都 存在着一条边有向图中的每两个顶 点之间都存在着方向相反的两条边, 则称此图为完全图。 显然完全无向图包含有条边完 全有向图包含有n(n-1)条边。例如 图(a)所示的图是一个具有4个顶点 的完全无向图共有6条边。图(b)所 示的图是一个具有4个顶点的完全有 (b) 向图共有12条边

3. 完全图 若无向图中的每两个顶点之间都 存在着一条边,有向图中的每两个顶 点之间都存在着方向相反的两条边, 则称此图为完全图。 显然,完全无向图包含有条边,完 全有向图包含有n(n-1)条边。例如, 图(a)所示的图是一个具有4个顶点 的完全无向图,共有6条边。图(b)所 示的图是一个具有4个顶点的完全有 向图,共有12条边。 1 2 0 3 1 2 0 3 (a) (b)

4.稠密图、稀疏图 当一个图接近完全图时,则称为稠 密图。相反,当一个图含有较少的边 4 数即当e<n(n-1)时则称为稀疏图。 5.子图 3)(0)(b) 设有两个图G=(VE)和G=(V,E”), 若V是Ⅴ的子集,即VV,且E是E的 4 子集,即EE,则称G是G的子图。 例如图(b)是图(a)的子图而图()不 ① 是图(a)的子图

4. 稠密图、稀疏图 当一个图接近完全图时,则称为稠 密图。相反,当一个图含有较少的边 数(即当e<<n(n-1))时,则称为稀疏图。 5. 子图 设有两个图G=(V,E)和G’=(V’,E’), 若V’是V的子集,即V’V,且E’是E的 子集,即E’E,则称G’是G的子图。 例如图(b)是图(a)的子图,而图(c)不 是图(a)的子图。 1 2 3 0 4 (a) (b) 1 2 3 0 4 1 2 3 0 4 (c)

6.路径和路径长度 在一个图G=(VE)中,从顶点v到顶点v 的一条路径是一个顶点序列 (vpyn,y2…,imy)若此图G是无向图,则边 (vpn),(vn,ya),…,(vm1,ym)vm3y)属于E(G) 若此图是有向图则,<Vny23,…,Vm nYm3vmy属于E(G) 路径长度是指一条路径上经过的边的 数目。若一条路径上除开始点和结束点可 以相同外,其余顶点均不相同,则称此路径为 简单路径。例如,有图中v21)就是一条 简单路径其长度为2

6. 路径和路径长度 在一个图G=(V,E)中,从顶点vi到顶点vj 的一条路径是一个顶点序列 (vi ,vi1 ,vi2 ,…,vim,vj ),若此图G是无向图,则边 (vi ,vi1 ),(vi1 ,vi2 ),…,(vim-1 ,vim),(vim,vj )属于E(G)； 若此图是有向图,则,,…,,属于E(G)。 路径长度是指一条路径上经过的边的 数目。若一条路径上除开始点和结束点可 以相同外,其余顶点均不相同,则称此路径为 简单路径。例如,有图中,(v0 ,v2 ,v1 )就是一条 简单路径,其长度为2。 1 2 0 3

7.回路或环 若一条路径上的开始点与结束点为 同一个顶点则此路径被称为回路或环。 开始点与结束点相同的简单路径被称为 简单回路或简单环。 例如右图中,(vn2Y1,0)就是一条简 单回路,其长度为3

7. 回路或环 若一条路径上的开始点与结束点为 同一个顶点,则此路径被称为回路或环。 开始点与结束点相同的简单路径被称为 简单回路或简单环。 例如,右图中,(v0 ,v2 ,v1 ,v0 )就是一条简 单回路,其长度为3。 1 2 0 3

9连通、连通图和连通分量 在无向图G中若从顶点v到顶点v有路径则称v 和v是连通的。 若图G中任意两个顶点都连通则称G为连通图否 则称为非连通图。 无向图G中的极大连通子图称为G的连通分量。 显然任何连通图的连通分量只有一个,即本身而非连 通图有多个连通分量

9. 连通、连通图和连通分量 在无向图G中,若从顶点vi到顶点vj有路径,则称vi 和vj是连通的。 若图G中任意两个顶点都连通,则称G为连通图,否 则称为非连通图。 无向图G中的极大连通子图称为G的连通分量。 显然,任何连通图的连通分量只有一个,即本身,而非连 通图有多个连通分量

9.强连通图和强连通分量 在有向图G中若从页点v到顶点v 有路径则称从v到v是连通的。 若图G中的任意两个顶点v和v都 连通,即从v到v和从v到v都存在路径, 则称图G是强连通图。例如右边两个 图都是强连通图。 有向图G中的极大强连通子图称为 G的强连通分量。显然强连通图只有 一个强连通分量,即本身非强连通图有 (b) 多个强连通分量

9. 强连通图和强连通分量 在有向图G中,若从顶点vi到顶点vj 有路径,则称从vi到vj是连通的。 若图G中的任意两个顶点vi和vj都 连通,即从vi到vj和从vj到vi都存在路径, 则称图G是强连通图。例如,右边两个 图都是强连通图。 有向图G中的极大强连通子图称为 G的强连通分量。显然,强连通图只有 一个强连通分量,即本身,非强连通图有 多个强连通分量。 1 2 0 3 （a） 1 2 0 （b）