7.1图的定义和术语 7、路径 在无向图G=(E)中,若存在一个顶点序列vp,va2,…,vpm, 使得( Vis vp1)、(vp1,vp2)、…、(vpmy均属于E,则称顶点v到v 存在一条路径。路径长度定义为路径上边或弧的数目。 若一条路径上除了v和v可以相同外,其余顶点均不相同,则 称此路径为一条简单路径 ●起点和终点相同的路径称为简单回路或简单环。 (a)简单路径 (b)非简单路径 C)回路 北京邮电大学自动化学院
北京邮电大学自动化学院 6 ⚫ 7、路径 ⚫ 若一条路径上除了vi 和vj 可以相同外， 其余顶点均不相同，则 称此路径为一条简单路径 。 7.1 图的定义和术语 ⚫ 在无向图 G＝(V, E) 中, 若存在一个顶点序列 vp1, vp2, …, vpm， 使得(vi , vp1)、(vp1, vp2)、 ...、(vpm, vj )均属于E，则称顶点vi到vj 存在一 条路径。路径长度定义为路径上边或弧的数目。 ⚫ 起点和终点相同的路径称为简单回路或简单环
7.1图的定义和术语 例 路径:1,2,3,5,6,3 ●路径长度:5 ●简单路径:1,2,3,5 6)·回路:1,2,3,5,6,3, GI 简单回路:3,5,6,3 路径:1,2,5,7,6,5,2,3 2 ●路径长度:7 简单路径:1,2,5,7,6 ●回路:1,2,5,7,6,5,2,1 G2 ●简单回路:1,2,3,1 北京邮电大学自动化学院
北京邮电大学自动化学院 7 例2 1 5 7 3 2 4 G2 6 例1 2 4 5 1 3 6 G1 ⚫ 路径：1，2，3，5，6，3 ⚫ 路径：1，2，5，7，6，5，2，3 7.1 图的定义和术语 ⚫ 路径长度：5 ⚫ 简单路径：1，2，3，5 ⚫ 回路：1，2，3，5，6，3，1 ⚫ 简单回路：3，5，6，3 ⚫ 路径长度：7 ⚫ 简单路径：1，2，5，7，6 ⚫ 回路：1，2，5，7，6，5，2，1 ⚫ 简单回路：1，2，3，1
7.1图的定义和术语 8、图的连通在无向图G中,若两个顶点v和之间有路径存 在,则称v和v是连通的。若G中任意两个顶点都是连通的, 则称G为连通图。 ●非连通图的极大连通子图叫做连通分量。 9、强连通图与强连通分量在有向图中,若对于每一对顶点v 和v都存在一条从V到v和从到v的路径则称此图是强连通 图。非强连通图的极大强连通子图叫做强连通分量。 例 例 例⑤ 6 强连通图 连通图 非连通图,连通分量 北京邮电大学自动化学院
北京邮电大学自动化学院 8 ⚫ 8、图的连通 在无向图G中，若两个顶点vi和vj之间有路径存 在，则称vi 和vj 是连通的。若G中任意两个顶点都是连通的， 则称G为连通图。 连通图 例 2 4 5 1 3 6 强连通图 3 5 6 例 例 2 4 5 1 3 6 非连通图，连通分量 ⚫ 9、强连通图与强连通分量 在有向图中, 若对于每一对顶点vi 和vj , 都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通 图。非强连通图的极大强连通子图叫做强连通分量。 7.1 图的定义和术语 ⚫ 非连通图的极大连通子图叫做连通分量
7.1图的定义和术语 10、带权图或网 ●若给图中每一条边附加一个实数作为权,则该图称 为带权图或网。 ●这些权可以表示从一个顶点到另一个顶点的距离或 花费的代价。 10 60 40 12 6 7 30 75 15 6 16 北京邮电大学自动化学院
北京邮电大学自动化学院 9 ⚫ 10、带权图或网 1 2 3 5 6 8 4 7 10 7 9 6 6 7 12 3 15 16 A B D C E 60 30 45 35 80 40 75 ⚫若给图中每一条边附加一个实数作为权，则该图称 为带权图或网。 7.1 图的定义和术语 ⚫这些权可以表示从一个顶点到另一个顶点的距离或 花费的代价
7.2图的存储结构 图的数组(邻接矩阵)存储表示 图的邻接表存储表示 有向图的十字链表存储表示 ●四、无向图的邻接多重表存储表示 北京邮电大学自动化学院 10
北京邮电大学自动化学院 10 ⚫一、图的数组(邻接矩阵)存储表示 7.2 图的存储结构 ⚫二、图的邻接表存储表示 ⚫三、有向图的十字链表存储表示 ⚫四、无向图的邻接多重表存储表示