清华大学：《数据结构》课程教学资源（PPT课件讲稿）第八章 图

第八章 图的基本概念 图的存储表示 图的遍历与连通性 最小生成树 最短路径 活动网络

图的基本概念 图的存储表示 图的遍历与连通性 最小生成树 最短路径 活动网络

图的基本概念 图定义图是由顶点集合 vertex)及顶点间的关 系集合组成的一种数据结构 Graph=(V,E) 其中V={x|x∈某个数据对象} 是顶点的有穷非空集合; E={(x,y)|x,y∈V} 或E={|x,y∈V&&Path(x,y)} 是顶点之间关系的有穷集合,也叫做边(edge) 集合。Pamh(x,y)表示从x到y的一条单向通路, 它是有方向的

图的基本概念 图定义 图是由顶点集合(vertex)及顶点间的关 系集合组成的一种数据结构： Graph＝( V, E ) 其中 V = { x | x  某个数据对象} 是顶点的有穷非空集合； E = {(x, y) | x, y  V } 或 E = { | x, y  V && Path (x, y)} 是顶点之间关系的有穷集合，也叫做边(edge) 集合。Path (x, y)表示从 x 到 y 的一条单向通路, 它是有方向的

有向图与无向图在有向图中,顶点对是 有序的。在无向图中,顶点对(x,y)是无序的。 完全图着有n个顶点的无向图有n(n-1)2条边 则此图为完全无向图。有n个顶点的有向图有 n(n-1)条边,则此图为完全有向图。 3)④4(5( (a)G1 (C)G3 (d)G4 邻接顶点如果(u,)是E(G)中的一条边,则 称u与v互为邻接顶点

有向图与无向图 在有向图中，顶点对是 有序的。在无向图中，顶点对(x, y)是无序的。 完全图 若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为完全无向图。有n 个顶点的有向图有 n(n-1) 条边, 则此图为完全有向图。 邻接顶点 如果 (u, v) 是 E(G) 中的一条边，则 称 u 与 v 互为邻接顶点

权某些图的边具有与它相关的数,称之为权。 这种带权图叫做网络。 0子图设有两个图G=(VE)和G=(V,E") 若vcV且EcE,则称图G是图G的子图 3①3 (a)G1 子图 子图 子图 b)63子图子图子图 顶点的度一个顶点v的度是与它相关联的边的 条数。记作TD()。在有向图中,顶点的度等于 该顶点的入度与出度之和

权 某些图的边具有与它相关的数, 称之为权。 这种带权图叫做网络。 子图 设有两个图 G＝(V, E) 和 G‘＝(V’, E‘)。 若 V’ V 且 E‘E, 则称 图G’是 图G 的子图。 顶点的度 一个顶点v的度是与它相关联的边的 条数。记作TD(v)。在有向图中, 顶点的度等于 该顶点的入度与出度之和

顶点ν的入度是以v为终点的有向边的条数,记 作ID(吵);顶点v的出度是以v为始点的有向边 的条数,记作OD( 路径在图G=(V,E)中,着从顶点v出发,沿 些边经过一些顶点vn,V23…,Vm,到达页点 则称顶点序列(vv1V2…my)为从顶点 "到顶点v的路径。它经过的边(Cv)、(m, p)…、(vm")应是属于E的边。 路径长度 非带权图的路径长度是指此路径上边的条数。 带权图的路径长度是指路径上各边的权之和

顶点 v 的入度是以 v 为终点的有向边的条数, 记 作 ID(v); 顶点 v 的出度是以 v 为始点的有向边 的条数, 记作 OD(v)。 路径 在图 G＝(V, E) 中, 若从顶点 vi 出发, 沿 一些边经过一些顶点 vp1 , vp2 , …, vpm，到达顶点 vj。则称顶点序列 ( vi vp1 vp2 ... vpm vj ) 为从顶点 vi 到顶点 vj 的路径。它经过的边(vi , vp1 )、(vp1 , vp2 )、...、(vpm, vj )应是属于E的边。 路径长度 非带权图的路径长度是指此路径上边的条数。 带权图的路径长度是指路径上各边的权之和

简单路径若路径上各顶点v,2…,n均不互相 重复,则称这样的路径为简单路径。 回路着路径上第一个顶点v1与最后一个顶点 vn重合,则称这样的路径为回路或环。 (a)简单路径 (b)非简单路径 (C)回路 连通图与连通分量在无向图中若从顶点v到 顶点v有路径,则称顶点v与v2是连通的。如果 图中任意一对顶点都是连通的,则称此图是连通 图。非连通图的极大连通子图叫做连通分量

简单路径 若路径上各顶点 v1 ,v2 ,...,vm 均不互相 重复, 则称这样的路径为简单路径。 回路 若路径上第一个顶点 v1 与最后一个顶点 vm 重合, 则称这样的路径为回路或环。 连通图与连通分量 在无向图中, 若从顶点v1到 顶点v2有路径, 则称顶点v1与v2是连通的。如果 图中任意一对顶点都是连通的, 则称此图是连通 图。非连通图的极大连通子图叫做连通分量

强连通图与强连通分量在有向图中,若对于每 对顶点和v都存在一条从到v和从v到v的 路径,则称此图是强连通图。非强连通图的极大 强连通子图叫做强连通分量。 生成树一个连通图的生成树是它的极小连通 子图,在n个顶点的情形下,有n-1条边。但有 向图则可能得到它的由若干有向树组成的生成 森林。 本章不予 讨论的图 (a)带自身环的图 (b)多重图

强连通图与强连通分量 在有向图中, 若对于每 一对顶点vi和vj , 都存在一条从vi到vj和从vj到vi的 路径, 则称此图是强连通图。非强连通图的极大 强连通子图叫做强连通分量。 生成树 一个连通图的生成树是它的极小连通 子图，在n个顶点的情形下，有n-1条边。但有 向图则可能得到它的由若干有向树组成的生成 森林。 本章不予 讨论的图

图的抽象数据类型 class graph i ublic Graph o; void Insertvertex( const Type vertex ) void Insertedge const int vl, const int v2, int weight ) void Remove vertex( const int v )3 void RemoveEdge( const int vl, const int v2 )3 int emPty( Type GetWeight( const int vl, const int v2) int GetFirstNeighbor const int v ); int GetNextNeighbor( const int vl, const int v2 )

图的抽象数据类型 class Graph { public: Graph ( ); void InsertVertex ( const Type & vertex ); void InsertEdge ( const int v1, const int v2, int weight ); void RemoveVertex ( const int v ); void RemoveEdge ( const int v1, const int v2 ); int IsEmpty ( ); Type GetWeight ( const int v1, const int v2 ); int GetFirstNeighbor ( const int v ); int GetNextNeighbor ( const int v1, const int v2 ); }

图的存储表示 邻接矩阵( Adjacency Matrix) 在图的邻接矩阵表示中,有一个记录各个顶点 信息的顶点表,还有一个表示各个顶点之间关 系的邻接矩阵。 设图A=(V,E)是一个有n个顶点的图,则图的 邻接矩阵是一个二维数组 A. edgelnlln],定义: A Edge[iljl 1,如果∈E或者(i,j)∈E 0.否则 。无向图的邻接矩阵是对称的,有向图的邻接矩 阵可能是不对称的

图的存储表示 在图的邻接矩阵表示中，有一个记录各个顶点 信息的顶点表，还有一个表示各个顶点之间关 系的邻接矩阵。 设图 A = (V, E)是一个有 n 个顶点的图，则图的 邻接矩阵是一个二维数组A.edge[n][n]，定义： 无向图的邻接矩阵是对称的，有向图的邻接矩 阵可能是不对称的。 邻接矩阵 (Adjacency Matrix)      = , , , ( , ) . [ ][ ] 否 则 如 果 0 1 A i j E i j E Edge i j 或者

G3 ①①②③④⑤⑦ 01010:000 ①①②③ ①①② 00100;000 0101)@ 010) 00010:000② AEdge=10100 A Edge=1010 AEdge=00001:0003 000)② 10000:000④ 1010③ 00000:010⑤ 00000:001⑥ 00000:100J⑦ 在有向图中,统计第i行1的个数可得顶点i的 出度,统计第j行1的个数可得顶点j的入度。 在无向图中统计第i行(列)1的个数可得顶点 i的度

在有向图中, 统计第 i 行 1 的个数可得顶点 i 的 出度，统计第 j 行 1 的个数可得顶点 j 的入度。 在无向图中, 统计第 i 行 (列) 1 的个数可得顶点 i 的度