8.路径、回路在无向图G中，若存在一个顶点序列V，Vij，Viz，VinV。使得（V,,V）(Vi,Vi)....，(Vin,V.)均属于E（G),则称顶点V到V存在一条路径。若一条路径上除起点和终点可以相同外，其余顶点均不相同，则称此路径为简单路径。起点和终点相同的路径称为回路，简单路径组成的回路称为简单回路。路径上经过的边的数目称为该路径的路径长度。9.有根图在一个有向图中，若从顶点V有路径可以到达图中的其它所有顶点，则称此有向图为有根图，顶点V称作图的根。10．生成树、生成森林连通图的生成树是一个极小连通子图，它包含图中全部n个顶点和n-1条不构成回路的边。非连通图的生成树则组成一个生成森林。若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。返回
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-5中的非强连通图，它的强连通分量见图7-7图7-7图7-5（b）的强连通分量
有向图中，极大的强连通子图为该图的强连通分量。 显然，任何强连通图的强连通分量只有一个，即它 本身，而非强连通图有多个强连通分量。 对于图7-5 中的非强连通图，它的强连通分量见图7-7。 6 3 5 图 7-7 图 7-5(b)的强连通分量 1 2 4
7.2图的存贮结构7.2.1邻接矩阵（数组表示法）1.图的邻接矩阵表示在邻接矩阵表示中，除了存放顶点本身信息外，还用一个矩阵表示各个顶点之间的关系。若（ii）EE(G)或《ii>EE(G),则矩阵中第i行第i列元素值为1，否则为0。图的邻接矩阵定义为：若(ij) EE(G)或<ij> EE(G)A[i][i]=其它情形O
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 其它情形
例如，对图7-8所示的无向图和有向图它们的邻接矩阵见图7-9。(a）无向图G3(b）有向图G4图7-8无向图G3及有向图G4I0C0100100010(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 邻接矩阵表示
2．从无向图的邻接矩阵可以得出如下结论（1）矩阵是对称的：（2）第i行或第i列1的个数为顶点i的度：（3）矩阵中1的个数的一半为图中边的数目：（4）很容易判断顶点i和顶点之间是否有边相连（看矩阵中行列值是否为1）。3．从有向图的邻接矩阵可以得出如下结论(1)矩阵不一定是对称的(2)第i行中1的个数为顶点i的出度：(3)第i列中1的个数为顶点的入度；(4)矩阵中1的个数为图中弧的数目(5)很容易判断顶点i和顶点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 是否有弧相连