8.连通、连通图和连通分量在无向图G中，若从顶点i(a)到顶点有路径，则称顶点和是连通的。若图G中任意两个顶点都连通，则称G为连通图，否则称为非连通图。无向图G中的极大连通子(b)图称为G的连通分量。显然，3任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。11
11 8 . 连通 、连通图和连通分量 在无向图 G 中 ，若从顶点 i 到顶点j有路径 ，则称顶点 i 和j 是连通 的 。 若图 G中任意两个顶点都 连通 ，则称 G 为连通图 ，否则 称为非连通图 。 无向图 G中的极大连通子 图称为 G的连通分量 。显然 ， 任何连通图的连通分量只有一 个，即本身，而非连通图有多 个连通分量。 1 2 0 3 1 2 0 (b) (a) 3
强连通图和强连通分量9.在有向图G中，若从顶点到顶点有路径，则称从顶点到是连通的。若图G中的任意两个顶点和都连通，即从顶点到和从顶点(a)到都存在路径，则称图G是强连通图。有向图G中的极大强连通子图称为G的强连通分量。显然，强(b)连通图只有一个强连通分量，即本身，非强连通图有多个强连通2分量。12
12 9. 强连通图和强连通分量 在有向图 G中，若从顶点 i 到 顶点j有路径，则称从顶点 i 到j 是 连通的。 若图 G中的任意两个顶点 i和j 都连通，即从顶点 i 到j和从顶点j 到 i都存在路径，则称图 G是强连 通图 。 有向图 G中的极大强连通子图 称为 G 的强连通分量。显然，强 连通图只有一个强连通分量，即 本身，非强连通图有多个强连通 分量。 1 2 0 3 (b) (a) 1 2 0 3
10.权和网图中每一条边都可以附有一个对应的数值，这种与边相关的数值称为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图称为带权图也称作网。13
13 10. 权和网 图中每一条边都可以附有一个对应的数值，这种与 边相关的数值称为权。权可以表示从一个顶点到另一个 顶点的距离或花费的代价。边上带有权的图称为带权图， 也称作网
例8.1有n个顶点的有向强连通图最多需要多少条边？最少需要多少条边？解：有n个顶点的有向强连通图最多有n(n-1）条边（构成一个有向完全图的情况）；最少有n条边（n个顶点依次首尾相接构成一个环的情况）。14
14 例8.1 有n个顶点的有向强连通图最多需要多少条边？ 最少需要多 少条边？ 解：有n个顶点的有向强连通图最多有n(n-1)条边 （构成一个有向完全图的情况）；最少有n条边（n个 顶点依次首尾相接构成一个环的情况）。 0 1 n-2 2 n-1
8.2图的存储结构8.2.1邻接矩阵存储方法邻接矩阵是表示顶点之间相邻关系的矩阵。设G-（V，E)是具有n（n>0）个顶点的图，顶点的顺序依次为0～n-1，则G的邻接矩阵A是n阶方阵，其定义如下：（1）如果G是无向图，则：A[illi]=1 : 若(i;j) EE(G) 0:其他（2）如果G是有向图，则：A[ili]=1：若<i,j>EE(G) 0:其他15
15 8.2 图的存储结构 8.2.1 邻接矩阵存储方法 邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V，E) 是具有n（n＞0）个顶点的图，顶点的顺序依次为0～n-1，则 G的邻接矩阵A是n阶方阵，其定义如下： （1）如果G是无向图，则： A[i][j]=1：若(i,j)∈E(G) 0:其他 （2）如果G是有向图，则： A[i][j]=1：若<i,j>∈E(G) 0:其他