第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的子图。 实例：
弧头和弧尾:有向图中存在<ⅵ,vj>,称弧的始点v为 弧尾,弧的终点v为弧头。 出边和入边:有向图中存在<ⅵ,j>,称该弧为始点ⅵ 的出边,终点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为弧头。 出边和入边：有向图中存在<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）