第8章图 图的基本概念 图的存储结构 Q图的遍历 生成树 最短路径 拓扑排序 关键路径
第8章 图 图的基本概念 图的存储结构 图的遍历 生成树 最短路径 拓扑排序 关键路径
图的基本概念 图:是一种数据结构,它的形式化定义为 Graph=(V, E),其中V是图中结点( Vertices)的非空有限集,E 是图中边( Edges)的有限集。 无向图:图上的每条边都没有方向,即两个顶点对 (V1,V2)和(V2,V1)代表同一边。 6有向图:图上的每条边都是有方向的,即两个顶点对 (V1,V2)和(V2,V1)代表两条边。 有向完全图:对于有向图,有n(n-1)条弧的有向图。 无向完全图:对于无向图,有n(n-1)/2条边的无向图 权:与图的边或弧相关的数叫做权( weight),权反应 了这条边或弧的某种特征的数据。 网:带权的图
图的基本概念 图：是一种数据结构，它的形式化定义为Graph=（V， E）,其中V是图中结点（Vertices）的非空有限集，E 是图中边（Edges）的有限集。 无向图： 图上的每条边都没有方向，即两个顶点对 （V1，V2）和（V2，V1）代表同一边。 有向图：图上的每条边都是有方向的，即两个顶点对 （V1，V2）和（V2，V1）代表两条边。 有向完全图：对于有向图，有n(n-1)条弧的有向图。 无向完全图：对于无向图，有n(n-1)/2条边的无向图。 权：与图的边或弧相关的数叫做权(weight)，权反应 了这条边或弧的某种特征的数据。 网：带权的图
实例 Av2 lVI 2 G1 G2 G4 (a)有向图G1 (b无向图G2 (c)有向完全图G3 (d)无向完全图G4 图81图的示例 73 20 12 15 图8-2网的示例
实例：
子图:有两个图G=(V,E)和G=(V′,E′),如果 V′∈V且E′∈E,则称G′为G的子图。 实例: V3 (a)图8-1中G1的子图 b)图8-1中G2的子图 图83子图的示例
子图：有两个图G=(V , E)和G′=(V′, E′)，如果 V′V且E′E，则称G′为G的子图。 实例：
弧头和弧尾:有向图中存在,称弧的始点v为 弧尾,弧的终点v为弧头。 出边和入边:有向图中存在,称该弧为始点ⅵ 的出边,终点v的入边。 度:无向图G=(V,E),边(v,v’)∈E,称顶点v和v 互为邻接点( adjacent);边(v,)依附 incident于顶 点ⅴ和v′,或说边(v,v’)和顶点v与v′相关联;顶点v 的度( degree是和顶点v相关联的边的数目,记为 TD(V。 入度:以顶点v为头的弧的数目,称为v的入度,记为 ID (v) 出度:以顶点v为尾的弧的数目,称为v的出度,记为 OD(v)
弧头和弧尾: 有向图中存在，称弧的始点vi为 弧尾，弧的终点vj为弧头。 出边和入边：有向图中存在，称该弧为始点vi 的出边，终点vj的入边。 度: 无向图G=(V , E)，边(v，v′)E，称顶点v和v′ 互为邻接点(adjacent);边(v，v′)依附(incident)于顶 点v和v′，或说边(v，v′)和顶点v与v′相关联;顶点v 的度(degree)是和顶点v相关联的边的数目，记为 TD(V)。 入度：以顶点v为头的弧的数目，称为v的入度，记为 ID（v）。 出度：以顶点v为尾的弧的数目，称为v的出度，记为 OD（v）
顶点的度:顶点的度TD(v)=ID(v)+OD(v)。 6路径:无向图G=(V,中从顶点v到顶点v的路径(path 是一个顶点序列(v,vi,O,v,1,vi,2……vi,m,y),其中(vi,j 1,Vi,j)∈E,1sj≤m;如果G是有向图,则路径也是有向的 顶点序列,应满足<Vi2j-1,ⅵij∈E,1≤j≤m。 路径的长度:路径上的边或弧的数目。 回路或环:第一个顶点和最后一个顶点相同的路径。 简单路径:序列中顶点不重复出现的路径。 简单回路:一条简单路径,其长度≥2,且路径的起始点和 终止点是同一顶点的路径。 连通图:在无向图中,从顶点v到顶点v有路径,则称v和 v是连通的;如果图中任意两个顶点ⅵ,vj∈V,ⅵ和ⅵ都 是连通的,则称G是连通图
顶点的度：顶点的度TD（v）=ID（v）+OD（v）。 路径：无向图G = (V , E)中从顶点v到顶点v的路径(path) 是一个顶点序列(v,vi,0,vi,1,vi,2vi,m,v)，其中(vi,j- 1,vi,j)E，1jm；如果G是有向图，则路径也是有向的 顶点序列，应满足vi,j-1,vi,jE，1jm。 路径的长度：路径上的边或弧的数目。 回路或环：第一个顶点和最后一个顶点相同的路径。 简单路径：序列中顶点不重复出现的路径。 简单回路：一条简单路径，其长度2，且路径的起始点和 终止点是同一顶点的路径。 连通图：在无向图中，从顶点v到顶点v有路径，则称v和 v是连通的；如果图中任意两个顶点vi ，vjV，vi和vj都 是连通的，则称G是连通图
连通分量:无向图中极大连通子图。 6强连通图:有向图G中,如果对于每一对vⅵi,vj∈V, ⅵA,从ⅵ到ⅵ和从v倒到ⅵ都存在路径,则称G是强连 通图 强连通分量:有向图中的极大连通子图称为有向图的强 连通分量 实例: 3 G1 (a)无向图G5 (b)G5的三个连通分量
连通分量：无向图中极大连通子图。 强连通图：有向图G中，如果对于每一对vi,vjV， vivj ，从vi到vj和从vj到vi都存在路径，则称G是强连 通图。 强连通分量：有向图中的极大连通子图称为有向图的强 连通分量。 实例： (a) 无向图G5 (b)G5的三个连通分量
生成树:为一个极小连通子图,含有图中的全部顶点, 只有足以构成一棵树的n-1条边 实例:@ 有向树:一个有向图恰好有一个顶点入度为0,其余顶 点入度为1,则为有向树。 生成森林:有向图的生成森林由若干棵有向树组成,含 有图中全部顶点,只含有足以构成若干棵不相交的有向 树的弧
生成树：为一个极小连通子图，含有图中的全部顶点， 只有足以构成一棵树的n-1条边。 实例： 有向树：一个有向图恰好有一个顶点入度为0，其余顶 点入度为1，则为有向树。 生成森林：有向图的生成森林由若干棵有向树组成，含 有图中全部顶点，只含有足以构成若干棵不相交的有向 树的弧
图的存储结构 邻接矩阵 邻接表
图的存储结构 邻接矩阵 邻接表
邻接矩阵表示法 概念:用二维数组存储图中顶点的信息,用矩阵表示图 中各个顶点(数据元素)之间的关系(边或弧)的信息; 设G=(V,E)是具有n个顶点的图,则G的邻接矩阵是 具有如下性质的n阶方阵: 1若(,V或是E中的边; A[]= 0若(,可或不是E中的边 网的邻接矩阵:网G=(V,E含有n1)个顶点V (v1,V2,),则元素为: 4ii=W若(v,)《是E中的 若(,V或不是E中的边
邻接矩阵表示法 概念：用二维数组存储图中顶点的信息，用矩阵表示图 中各个顶点（数据元素）之间的关系（边或弧）的信息； 设G=（V，E）是具有n个顶点的图，则G的邻接矩阵是 具有如下性质的n阶方阵 ： 网的邻接矩阵：网G=(V，E)含有n(1)个顶点V= （v1,v2,vn），则元素为：