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

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

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

(vertex) ：

有向图与无向图在有向图中,顶点对是 有序的。在无向图中,顶点对(x,y)是无序的。 完全图若有n个顶点的无向图有m(m-1)2条边 则此图为完全无向图。有n个顶点的有向图有 n(n-1)条边,则此图为完全有向图。 ③④4⑤( (a)G1 (b)G2 (C)G3 邻接顶点如果(a,y是E(G)中的一条边,则 称u与p互为邻接顶点

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

n顶点v的入度是以v为终点的有向边的条数,记 作ID(吵);顶点v的出度是以v为始点的有向边 的条数,记作OD(吵) 路径在图G=(V,E)中,若从顶点v出发,沿 些边经过一些顶点vp,V2…,Vm,到达顶点 "y则称顶点序列(vpV2…Vmv)为从顶点 v到顶点v的路径。它经过的边(pn)、(vp, 、(my)应是属于E的边。 路径长度 ◆非带权图的路径长度是指此路径上边的条数 ◆带权图的路径长度是指路径上各边的权之和

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

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

图的抽象数据类型 class Grap h i ublic. Graph o; void Insert vertex( const Type vertex )i void Insertedge const int vl, const int v2, int weight ) void Remove vertex( const int v ); void RemoveEdge( const int vl, const int v2) int IsEmpty (; Type GetWeight( const int vl, const int v2 )i 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个顶点的图,则图的 邻接矩阵是一个二维数组 Aedgell]m,定义: 1,如果∈E或者(i,j)∈E A Edge lilil 0.,香则 无向图的邻接矩阵是对称的,有向图的邻接矩 阵可能是不对称的

    ,, , ( , ) . [ ][ ] 否则如果 01 A i j E i j E Edge i j 或者

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