简单路径若路径上各顶点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,如果<ij>∈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 的度