北京邮电大学自动化学院：《数据结构》第七章 图

第7章图 ④⑤ 7.「图的定义和术语 1、图、顶点、边 GI 图G是由集合VG和E(G)组成记为G=(vE),其中V(G是顶 点的非空有限集合,E(G)是边的有限集合,边是点的无序对 或有序对。 2、有向图、弧、无向图 ●若图中的边是顶点的有序对,则称此图为有向图。 有向边又称为弧,通常用尖括号表示一条有向边,<vw表 示从顶点v到w顶点的一条弧,v称为边的始点(或弧尾),w 称为边的终点(或弧头)。 北京邮电大学自动化学院

北京邮电大学自动化学院 1 第7章 图 ⚫ 7.1 图的定义和术语 ⚫ 1、图、顶点、边 ⚫ 图G是由集合V(G)和E(G)组成,记为G=(V,E)，其中V(G)是顶 点的非空有限集合，E(G)是边的有限集合，边是点的无序对 或有序对。 ⚫ 2、有向图、弧、无向图 2 4 5 1 3 6 G1 ⚫ 若图中的边是顶点的有序对，则称此图为有向图。 ⚫ 有向边又称为弧，通常用尖括号表示一条有向边，表 示从顶点v到w顶点的一条弧，v称为边的始点（或弧尾），w 称为边的终点（或弧头）

7.1图的定义和术语 ·图G中:V(G1)={1,23,4,,6} E(G1)={≤1,2>,21>,,,≤3,5>,,} 例 例 6③2④⑥ GI G2 无向图若图中的边是顶点的无序对,则称此图为无向图。通 常用园括号表示无向边。(V,w)或(Wv),并且(vwy)=(w,v) ·图G2中:V(G2)={1,234,5,67 E(G1)={(1,2),(1,3)(2,3),(2,4)2(25),5,6),(5,7) 北京邮电大学自动化学院

北京邮电大学自动化学院 2 例 2 4 5 1 3 6 G1 ⚫ 图G1中： V(G1)={1,2,3,4,5,6} ⚫ E(G1)={, , , , , , } 例 1 5 7 3 2 4 G2 6 ⚫ 图G2中： V(G2)={1,2,3,4,5,6,7} ⚫ 无向图 若图中的边是顶点的无序对，则称此图为无向图。通 常用园括号表示无向边。（v,w）或（w,v)，并且（v,w)=(w,v) 7.1 图的定义和术语 ⚫ E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)}

7.1图的定义和术语 ●3、有向完全图、无向完全图 有向完全图:具有n(n-1)条弧的有向图称为有向完全图 ●无向完全图:n个顶点的无向图最大边数是n(n-1)2,具有 n(n-1)2条边的无向图称为无向完全图。 有向完全图 无向完全图 4、相邻顶点、相关联弧或边 若≤E或(V1v2)E,则V1,V2是相邻顶点,弧 或边(v1V2)是与顶点V和v2相关联弧或边。 北京邮电大学自动化学院

北京邮电大学自动化学院 3 ⚫ 3、有向完全图、无向完全图 ⚫ 4、相邻顶点、相关联弧或边 ⚫ 无向完全图：n个顶点的无向图最大边数是n(n-1)/2，具有 n(n-1)/2条边的无向图称为无向完全图。 2 1 3 有向完全图 2 1 3 无向完全图 7.1 图的定义和术语 ⚫ 若 E或(V1 ,V2 ) E ，则V1，V2是相邻顶点，弧 或边(V1 ,V2 )是与顶点V1和V2相关联弧或边。 ⚫ 有向完全图：具有n(n-1)条弧的有向图称为有向完全图

7.1图的定义和术语 ●5、度 个顶点V的度是与该顶点相关联的边的数目,记为TD(v)。 ●对于有向图,则把以顶点v为弧尾的数目称为点V的出度, 记为OD(V),把以顶点V为头的弧的数目称为顶点V的入 度,记为ID(v)。顶点V的度为 ●TD(v)=|D(V)+OD(V) 例1 例2 G1 G2 顶点2入度:1出度:3 顶点5的度:3 顶点4入度:1出度:0 顶点2的度:4 北京邮电大学自动化学院 4

北京邮电大学自动化学院 4 ⚫ 5、度 例1 2 4 5 1 3 6 G1 ⚫ 顶点2入度：1 出度：3 ⚫ 顶点4入度：1 出度：0 例2 1 5 7 3 2 4 G2 6 ⚫ 顶点5的度：3 ⚫ 顶点2的度：4 7.1 图的定义和术语 ⚫ 一个顶点V的度是与该顶点相关联的边的数目，记为TD（V）。 ⚫ 对于有向图，则把以顶点V为弧尾的数目称为点V的出度， 记为OD（V），把以顶点V为头的弧的数目称为顶点V的入 度，记为ID（V）。 顶点V的度为： ⚫ TD（V）=ID（V）+OD（V）

7.1图的定义和术语 6、子图 设有两个图G=(vE和G=(v,E)。若VsV且 EgE,则称图G是图G的子图。 (a)G1 子图 子图 子图 b)63子图子图子图 北京邮电大学自动化学院

北京邮电大学自动化学院 5 ⚫ 6、子图 ⚫ 设有两个图 G＝(V, E) 和 G‘＝(V’, E‘)。若 V’ V 且 E‘E, 则称 图G’ 是 图G 的子图。 7.1 图的定义和术语

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 图的存储结构 ⚫二、图的邻接表存储表示 ⚫三、有向图的十字链表存储表示 ⚫四、无向图的邻接多重表存储表示