有向图的极大强连通子图称为G的强连通分量。 根据强连通图的定义,可知强连通图的唯一强连通 分量是其自身,而非强连通的有向图有多个强连分 量。例如,图82(b)所示的有向图G是一个具有 4个顶点的强连通图图85(a)所示的有向图G 不是强连通图(V2、V3V没有到达v的路径), 它的两个强连通分量H3H如图85(b)所示。 (a)非强连通图G6(b)G的两个强连通分量H和H4
有向图的极大强连通子图称为G的强连通分量。 根据强连通图的定义，可知强连通图的唯一强连通 分量是其自身，而非强连通的有向图有多个强连分 量。例如，图8.2（b）所示的有向图G4是一个具有 4个顶点的强连通图，图8.5（a）所示的有向图G6 不是强连通图（v2、v3、v4没有到达v1的路径）， 它的两个强连通分量H3与H4如图8.5（b）所示。 v1 v2 v3 v4 v1 v2 v3 v4 （a）非强连通图G6 （b）G6的两个强连通分量H3和H4
七、网络 有时在图的每条边上附上相关的数值,这种与 图的边相关的数值叫权。 权可以表示两个顶点之间的距离、耗费等具有 某种意义的数。若将图的每条边都赋上一个权,贝 称这种带权图为网络。 5678 6450 )45V (a)无向网络G (b)有向网络G8
七、网络 有时在图的每条边上附上相关的数值，这种与 图的边相关的数值叫权。 权可以表示两个顶点之间的距离、耗费等具有 某种意义的数。若将图的每条边都赋上一个权，则 称这种带权图为网络。 V0 V1 V3 V2 34 56 78 25 V0 V1 V2 45 64 50 （a）无向网络G7 （b）有向网络G8
作业 8.1对于无向图829,试给出 (1)图中每个顶点的度 (2)该图的邻接矩阵 4)该图的连通分量。 图829无向图
作业： 8.1 对于无向图8.29，试给出 （1）图中每个顶点的度； （2）该图的邻接矩阵； （4）该图的连通分量。 v0 v3 v4 v2 v1 v5 v6 图8.29 无向图
8.2给定有向图8.30,试给出 (1)顶点D的入度与出度 (2)该图的出边表与入边表 (3)该图的强连通分量。 图830有向图
8.2 给定有向图8.30，试给出 （1）顶点D的入度与出度； （2）该图的出边表与入边表； （3）该图的强连通分量。 A B C D E 图8.30 有向图
82图的基本运算 图是一种复杂数据结构,由图的定义及图的一组基 本操作构成了图的抽象数据类型。 ADT Grapht 数据对象∨:V是具有相同特性的数据元素的集合,称 为顶点集。 数据关系R: R={v,W>|V,WeV且P(v,W),P(v,W)定义 了边(或弧)(v,W)的信息}
8.2 图的基本运算 图是一种复杂数据结构，由图的定义及图的一组基 本操作构成了图的抽象数据类型。 ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称 为顶点集。 数据关系R： R={<v，w>|v，wV且P（v，w），P（v，w）定义 了边（或弧）（v，w）的信息}