有向图中,极大的强连通子图为该图的强连通分量。 显然,任何强连通图的强连通分量只有一个,即它 y本身,而非强连通图有多个强连通分量 对于图7-5中的非强连通图,它的强连通分量见图7-7。 图7-7图7-5(b)的强连通分量
有向图中，极大的强连通子图为该 图的强连通分量。 显然，任何强连通图的强连通分量只有一个，即它 本身，而非强连通图有多个强连通分量。 对于图7-5 中的非强连通图，它的强连通分量见图7-7。 6 3 5 图 7-7 图 7-5(b)的强连通分量 1 2 4
x:?8.路径、回路 在无向图G中,若存在一个顶点序列V,V1,V2,…,Vn .Va使得(VnV1)(Vn1V)…,(VmnV)均属于E(G), 则称顶点V到V存在一条路径。若一条路径上除起点和终 点可以相同外,其余顶点均不相同,则称此路径为简单路 径。起点和终点相同的路径称为回路,简单路径组成的回 路称为简单回路。路径上经过的边的数目称为该路径的路 径长度。 9.有根图 在一个有向图中,若从顶点V有路径可以到达图中的 其它所有顶点,则称此有向图为有根图,顶点Ⅴ称作 图的根。 10.生成树、生成森林 连通图的生成树是一个极小连通子图,它包含图中全部n 顶点和n-1条不构成回路的边。非边通图的生成树则组 成一个生成森林。若图中有n个顶点,m个连通分量,则 生成森林中有nm条边
8．路径、回路 在无向图G中，若存在一个顶点序列Vp ,Vi1，Vi2，…，Vin， Vq, 使得（Vp ,Vi1）,(Vi1 ,Vi2 ),…..，(Vin,Vq )均属于E（G）， 则称顶点Vp到Vq存在一条路径。若一条路径上除起点和终 点可以相同外，其余顶点均不相同，则称此路径为简单路 径。起点和终点相同的路径称为回路，简单路径组成的回 路称为简单回路。路径上经过的边的数目称为该路径的路 径长度。 9． 有根图 在一个有向图中，若从顶点V有路径可以到达图中的 其它所有顶点，则称此有向图为有根图，顶点V称作 图的根。 10． 生成树、生成森林 连通图的生成树是一个极小连通子图，它包含图中全部n 个顶点和n-1条不构成回路的边。非边通图的生成树则组 成一个生成森林。若图中有n个顶点，m个连通分量，则 生成森林中有n-m条边
7.2图的存贮结构 7.21邻接矩阵 1.图的邻接矩阵表示 在邻接矩阵表示中,除了存放顶点本身信息外,还 用一个矩阵表示各个顶点之间的关系。若(ij) ∈E(G)或(ij)∈F(G)则矩阵中第i行第j列元素值为 1,否则为0。 图的邻接矩阵定义为: 若(ij)∈E(G)或(ij)∈E(G) A[[]= 其它情形
7.2 图的存贮结构 7.2.1 邻接矩阵 1． 图的邻接矩阵表示 在邻接矩阵表示中，除了存放顶点本身信息外，还 用一个矩阵表示各个顶点之间的关系。若（i,j） ∈E(G)或〈i,j〉∈E(G),则矩阵中第i行 第j列元素值为 1，否则为0 。 图的邻接矩阵定义为： 1 若（i,j）∈E(G)或〈i,j〉∈E(G) A[i][j]= 0 其它情形
小?如,对图73所示的无向图和有向图,它们的邻接矩阵 (a)无向图G3 (b)有向图G4 图7-8无向图G3及有向图G4 0 010 0 001 00 1110 (a)G3的邻接矩阵 (b)G4的邻接矩 图7-9邻接矩阵表示
例如, 对图7-8所示的无向图和有向图,它们的邻接矩阵 见图7-9。 3 1 2 (a) 无向图 G3 (b)有向图 G4 图 7-8 无向图 G3 及有向图 G4 1 2 4 3 1 1 1 0 0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 0 0 1 0 1 1 (a) G3 的邻接矩阵 (b) G4 的邻接矩 图 7-9 邻接矩阵表示
x2.从无向图的邻接矩阵可以得出如下结论 (1)矩阵是对称的 (2)第行或第i列1的个数为顶点i的度 (3)矩阵中1的个数的一半为图中边的数目 (4)很容易判断顶点i和顶点之间是否有边相连(看 矩阵中行列值是否为1) 3.从有向图的邻接矩阵可以得出如下结论 (1)矩阵不一定是对称的; (2)第i行中1的个数为顶点i的出度 (3)第列中1的个数为顶点i的入度 (4)矩阵中1的个数为图中弧的数目; (5)很容易判断顶点i和顶点是否有弧相连
2． 从无向图的邻接矩阵可以得出如下结论 （1）矩阵是对称的; （2）第i行或第i 列1的个数为顶点i 的度; （3）矩阵中1的个数的一半为图中边的数目; （4）很容易判断顶点i 和顶点j之间是否有边相连(看 矩阵中i行j列值是否为1)。 3． 从有向图的邻接矩阵可以得出如下结论 （1） 矩阵不一定是对称的; （2） 第i 行中1的个数为顶点i 的出度; （3） 第i列中1的个数为顶点 i的入度; （4） 矩阵中1的个数为图中弧的数目; （5） 很容易判断顶点i 和顶点j 是否有弧相连