《数据结构》课程教学课件（讲稿，C语言描述）第7章 图

童图第7章数据结构（C语言描述）

第7章 图 数据结构（C语言描述）

目录7. 1图的基本概念7.2图的存贮结构7.3图的遍历7.4生成树和最小生成树7.5拓扑排序7.6最短路径退出

目录 7.6 最短路径 7.1 图的基本概念 7.2 图的存贮结构 7.3 图的遍历 7.4 生成树和最小生成树 7.5 拓扑排序 退 出

7.1E图的基本概念7.1.1图的定义图是由顶点集V和顶点间的关系集合E（边的集合）组成的一种数据结构，可以用二元组定义为：G=（VE）。例如，对于图7-1所示的无向图G1和有向图G2，它们的数据结构可以描述为：G=(V,E),其中V={a,b,c,d),E,=((a,b),(a,c),(a,d),(b,d),(c,d)), 而 G,=(V2,E2) 其中V,=[1,2,3}, E,=[,,,} 。(a）无向图Gl(b）有向图G2图7-1无向图和有向图

7.1 图的基本概念 7.1.1 图的定义 图是由顶点集V和顶点间的关系集合E（边的集合）组成 的一种数据结构，可以用二元组定义为：G=（V,E）。 例如，对于图7-1所示的无向图G1和有向图G2，它们的数 据 结 构 可 以 描 述 为 ： G1 =(V1 ,E1 ), 其 中 V1 ={a,b,c,d},E1 ={(a,b),(a,c),(a,d),(b,d),(c,d)}, 而 G2 =(V2 ,E2 ) ， 其中V2 ={1,2,3}, E2 ={,,,}。 d A A c A a b 1 2 3 (a) 无向图 G1 (b) 有向图 G2 图 7-1 无向图和有向图

7.1.2图的基本术语1.有向图和无向图在图中，若用箭头标明了边是有方向性的，则称这样的图为有向图，否则称为无向图。如图7-1中，G为无向图G,为有向图。在无向图中，一条边（xy）与（y.x）表示的结果相同，用圆括号表示，在有向图中，一条边与表示的结果不相同，故用尖括号表示。《xy>表示从顶点x发向顶点y的边，x为始点，y为终点。有向边也称为弧，x为弧尾，y为弧头，则表示为一条弧，而y,x>表示y为弧尾，x为弧头的另一条弧。2．完全图、稠密图、稀疏图具有n个顶点，n(n-1)/2条边的图，称为完全无向图，具有n个顶点，n(n-1）条弧的有向图，称为完全有向图。完全无向图和完全有向图都称为完全图

7.1.2 图的基本术语 1. 有向图和无向图 在图中，若用箭头标明了边是有方向性的，则称这样的 图为有向图，否则称为无向图。如图7-1中，G1为无向图， G2为有向图。 在无向图中，一条边（x,y）与（y,x）表示的结果相同， 用圆括号表示，在有向图中，一条边与表示 的结果不相同，故用尖括号表示。〈x,y>表示从顶点x发 向顶点y的边，x为始点，y为终点。有向边也称为弧，x 为弧尾，y为弧头,则〈x,y>表示为一条弧,而〈y,x>表示y 为弧尾，x为弧头的另一条弧 。 2. 完全图、稠密图、稀疏图 具有n个顶点，n(n-1)/2条边的图，称为完全无向图，具有 n个顶点，n(n-1) 条弧的有向图,称为完全有向图。完全无 向图和完全有向图都称为完全图

对于一般无向图，顶点数为n，边数为e，则O<e≤n(n1)/2。对于一般有向图，顶点数为n，弧数为e，则O<e<n(n-1)。当一个图接近完全图时，则称它为稠密图，相反地，当一个图中含有较少的边或弧时，则称它为稀疏图。3．度、入度、出度在图中，一个顶点依附的边或弧的数目，称为该顶点的度。在有向图中，一个顶点依附的弧头数目，称为该顶点的入度。一个顶点依附的弧尾数目，称为该顶点的出度，某个顶点的入度和出度之和称为该顶点的度另外，若图中有n个顶点，e条边或弧，第i个顶点的度为d，则有e=2di=l

对于一般无向图，顶点数为n，边数为e，则 0≤e ≤n(n- 1)/2。 对于一般有向图，顶点数为n，弧数为e， 则 0≤e≤n(n- 1) 。 当一个图接近完全图时，则称它为稠密图，相反地， 当一个图中含有较少的边或弧时，则称它为稀疏图。 3. 度、入度、出度 在图中，一个顶点依附的边或弧的数目，称为该顶点的 度。在有向图中，一个顶点依附的弧头数目，称为该顶 点的入度。一个顶点依附的弧尾数目，称为该顶点的出 度，某个顶点的入度和出度之和称为该顶点的度。 另外，若图中有n个顶点，e条边或弧，第i个顶点的度为di， 则有e= 2 1  n i di 1

4.子图满足若有两个图G,和G2， G,=(V,E,)， G,=(V,E,)， 如下条件：V,≤V，，EzE,，即V,为V,的子集，E,为E，的子集，称图G，为图G的子图。图和子图的示例具体见图7-2。(a)图 G(b)图G的两个子图图7-2图与子图示意

4. 子图 若有两个图G1和G2， G1 =(V1 ,E1 )， G2 =(V2 ,E2 )， 满足 如下条件： V2V1 ，E2 E1，即V2为V1的子集，E2为 E1的子集，称图G2为图G1的子图。 图和子图的示例具体见图7-2。 3 4 1 2 3 4 1 2 4 1 2 (a)图 G (b)图 G 的两个子图 图 7-2 图与子图示意 3 4 1 2

5.权在图的边或弧中给出相关的数，称为权。权可以代表一个顶点到另一个顶点的距离，耗费等，带权图一般称为网。带权图的示例具体见图7-3。(a）无向网(b)有向网图7-3无向带权图和有向带权图

5． 权 在图的边或弧中给出相关的数，称为权。 权可以代 表一个顶点到另一个顶点的距离，耗费等，带权图 一般称为网。 带权图的示例具体见图7-3。 (a) 无向网 (b)有向网 图 7-3 无向带权图和有向带权图 5 3 1 2 4 4 1 6 7 2 3 5 8 A B C 2 1 5 3 4

6.连通图和强连通图在无向图中，若从顶点到顶点有路径，则称顶点和顶点是连通的。若任意两个顶点都是连通的，则称此无向图为连通图，否则称为非连通图连通图和非连通图示例见图7-4。O连通图非连通图(a)(b)图7-4连通图和非连通图

6． 连通图和强连通图 在无向图中，若从顶点i到顶点j有路径，则称顶点i和 顶点j是连通的。若任意两个顶点都是连通的，则称此 无向图为连通图，否则称为非连通图。 连通图和非连通图示例见图7-4。 3 1 2 4 1 2 3 5 4 （a） 连通图 (b) 非连通图 图 7-4 连通图和非连通图

在有向图中，若从顶点到顶点有路径，则称顶点和顶点是连通的，若图中任意两个顶点都是连通的，则称此有向图为强连通图，否则称为非强连通图强连通图和非强连通图示例见图7-5。(a）强连通图(b）非强连通图图7-5强连通图和非强连通图

在有向图中，若从顶点i到顶点j有路径，则称顶点i和 顶点j是连通的，若图中任意两个顶点都是连通的，则 称此有向图为强连通图，否则称为非强连通图。 强连通图和非强连通图示例见图7-5。 A B D C 1 2 1 4 5 6 3 (a)强连通图 (b)非强连通图 图 7-5 强连通图和非强连通图

7.连通分量和强连通分量无向图中，极大的连通子图为该图的连通分量显然，任何连通图的连通分量只有一个，即它本身，而非连通图有多个连通分量对于图7-4中的非连通图，它的连通分量见图7-6。图7-6图7-4(b)的连通分量

7． 连通分量和强连通分量 无向图中，极大的连通子图为该图的连通分量。 显然，任何连通图的连通分量只有一个，即它本 身，而非连通图有多个连通分量。 对于图7-4 中的非连通图，它的连通分量见图7-6。 1 2 3 5 4 图 7-6 图 7-4(b)的连通分量