数据结构第6章课件

1、第6章 图本章概述 图是一种重要的非线性结构，并且是一种比线性表和树更为复杂的数据结构。图的特点是每个顶点都可以与其他顶点相连；在图结构中，每个顶点的地位是一样的，图中任意两个顶点之间都可以相关。 图的应用极为广泛，特别是图论的迅速发展，使得图的应用已渗入到运筹学、逻辑学、计算机科学及语言学等其他分支学科中。6.1 图的定义和术语 图是由一个顶点集V和一个弧集R构成的数据结构。 图的抽象数据类型数学表述为：Graph =（V，R），且VR | t，hV且P(t，h) 其中，VR表示两个顶点之间的关系，表示从t到h的一条弧，P( t，h)定义了弧的意义。 图中的数据元素通常称为顶点（vertex

2、）。 V是顶点的有穷非空集合。 VR表示两个顶点之间的关系的集合。 若VR，则表示从t到h的一条弧，且称t为弧尾（tail），h为弧头(head)，此时的图称为有向图。 若VR必有VR,即VR是对称的，则用无序对（t，h）代替这两个有序对，表示t和h这两个顶点之间的一条边，此时的图称为无向图。 下图(a)所示为无向图，(b)所示为有向图。 【例6-1】使用集合的表示方法，上面的两个图可以用如下的方法表示：Ga=(Va,Ea)；Gb=(Vb,Eb)Va=1,2,3,4；Ea=(1,2),(1,3),(1,4),(2,3)Vb=1,2,3,4,5；Eb=,注意：无向图的顶点无序偶对使用一对圆括号表

3、示，有向图的顶点有序偶对使用一对尖括号表示。 每条边都是有向边的图，称为有向图；每条边都是无向边的图，称为无向图。既有有向边又有无向边的图，称为混合图。 用n表示图中顶点的数目，用e表示图中边的数目。 不考虑顶点到自身的边，对于无向图，e的取值范围是0n(n-1)/2，具有n(n-1)/2条边的无向图称为无向完全图。 对于有向图，e的取值范围是0n(n-1)，具有n(n-1)条边的有向图称为有向完全图。在工程应用中，边数e小于nlog n的图称为稀疏图，反之称为稠密图。 假设有两个图G=(V，E)和G=(V,E)，如果 V V且E E，则称G为G的子图。 下图所示是子图的一些例子。子图是在原图

4、上删去若干条边或若干个点剩下的图。 删边指删去图中的某一条边但仍保留边的顶点。 删点指删去图中某一点以及与这点相连的所有边。 图中删去一点所得的子图称为主子图。 设有一个n阶无向图，在其中添加一些边后，可使其成为n阶完全图。 由这些新添加的边和其顶点构成的图称为原图的补图。 对于无向图G=(V，E)，顶点v的度是和v相连的边的数目，记为D(v)。 对于有向图G=(V，R)，以顶点t为弧头的弧的数目称为顶点t的入度，记为ID(t)；以顶点t为弧尾的弧的数目称为顶点t的出度，记为OD(t)；顶点t的度记为D(t)=ID(t)+OD(t)。 特殊情况下，度数为零的顶点称为孤立点，度数为1的顶点称为悬

5、挂点。 一般地，如果顶点vi的度记为D（vi），那么一个有n个顶点，e条边的图，满足如下关系： 定理1：设图G是具有v个顶点，e条边的无向图，则有D(v)=2e。 定理2：设图G是具有v个顶点，e条边的有向图，则有ID(v)=OD(v)=e。 路径长度是路径上边的数目或弧的数目。 一条边的两端重合，称为自回路。 第一个顶点和最后一个顶点相同的路径称为回路或环。 在顶点序列中，顶点不重复出现的路径称为简单路径。 除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。 在无向图G=(V，E)中，如果存在一条从顶点v到顶点w的路径，则称从v到w可达。 如果图中任意两点是可

6、达的，则称v和w是连通的，否则不连通。 对于图中任意两个顶点v、wV，v和w都是连通的，则称G是连通图。 有向图G=中，如果对于每一对t、hV，从t到h和从h到t都存在路径，则称G是强连通图。 有向图中的极大强连通子图称为有向图的强连通分量。 例如，下图不是强连通图，但它有两个强连通分量。 在图的顶点或边上表明某种信息的数称为权，含有权的图，称为赋权图。 例如，下图就是一个赋权图。 最短路径问题的算法： 先求出到某一顶点的最短路径，然后利用这个结果再去确定到另一顶点的最短路径，如此继续下去，直到找到最短路径为止。 如果图中存在一条通过图中各边一次且仅一次的回路，则称此回路为欧拉回路，具有欧拉回

7、路的图称为欧拉图。 如果图中存在一条通过图中各边一次且仅一次的通路，则称此通路为欧拉通路，具有欧拉通路的图称为半欧拉图。 定理3：一个无向连通图是欧拉图的充要条件是图中各点的度数为偶数。 定理4：一个无向连通图是半欧拉图的充要条件是图中至多有两个奇数度点。 定理5：设图G是有向连通图，图G是欧拉图的充要条件是图中每个顶点的入度和出度相等。 定理6：设图G是有向连通图，图G是半欧拉图的充要条件是至多有两个顶点的出度和入度不相等，其中一个顶点的入度比它的出度大1，另一个顶点的入度比它的出度小1，而其他顶点的入度和出度相等。 一个连通图的生成树是一个极小的连通子图，它含有图中全部顶点，但只有构成一棵

8、树的n-1条边。 一棵有n个顶点的生成树有且仅有n-1条边。 如果一个图有n个顶点和小于n-1条边，则图一定是非连通图，如果它多于n-1条边，则一定有环。6.2 图的存储结构 设G=（V，E）是具有n个顶点的图，则G的邻接矩阵定义为： 【例6-2】将下图(a)所示的无向图和图(b)所示的有向图用邻接矩阵表示。6.2.1 邻接矩阵 解：以上无向图和有向图分别用邻接矩阵M1和M2表示如下： 设G=（V，E）是具有n个顶点的赋权图，则G的邻接矩阵定义为： 【例6-3】将下图所示的赋权图用邻接矩阵表示。解：赋权图可以用邻接矩阵M3或M4表示如下： 图的邻接矩阵存储结构的描述形式如下：#define M

9、AX_VERTEX_NUMBER 100 最大顶点数typedef char VertexType;顶点类型typedef int edge;边上的权值类型typedef struct MGraph存储图的结构体VertexType vArrayMAX_VERTEX_NUMBER; 顶点数组edge eArrayMAX_VERTEX_NUMBERMAX_VERTEX_NUMBER;邻接矩阵int n; 顶点数int e; 边数; 算法6.1是在邻接矩阵存储结构MGraph上对图构造的实现算法。 注意：在简单应用中，可直接用二维数组作为邻接矩阵，顶点数和边数均可省略。 对于无向图，顶点vi的度是

10、邻接矩阵中第i行（或第i列）的元素之和。 对于有向图，顶点vi的度是邻接矩阵中第i行和第i列的元素之和，且第i行的元素之和为顶点vi的出度，第i列的元素之和为顶点vi的入度。 对于图中的每个顶点vi，把所有邻接于vi的顶点vj链成一个带头结点的单链表，这个单链表称为顶点vi的邻接表。 邻接表的结构由两部分组成： 头结点：用于存储顶点信息和指向表结点的指针； 表结点：用于存储头结点中顶点相邻接的顶点信息和指向表结点的指针。6.2.2 邻接表【例6-4】给出下图中无向图G的邻接表表示。 解：无向图G的邻接表表示如下图所示。 注意：在编程时，头结点以数组的形式存储，表结点以单链表的形式存储。显然，在

11、稀疏图中，用邻接表存储比用邻接矩阵存储节省存储空间。【例6-5】给出下图中有向图G的邻接表表示。 解：有向图G的邻接表表示如下图所示。 为了方便确定顶点的入度，可以建立有向图的逆邻接表，下图就是例【6-5】中有向图的逆邻接表。 在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点之间是否有边相连，则要搜索单链表，不如邻接矩阵方便。 图的邻接表存储结构的表示形式如下：#define MAX_VERTEX_NUMBER 100 最大顶点数typedef char VertexType; 顶点类型typedef struct eNode 表结点int adjVer;eNode

12、 *pNext;typedef struct vNode 头结点VertexType vertex;eNode *pFirst;typedef struct ALGraph 邻接表结构体vNode adjListMAX_VERTEX_NUMBER;头结点数组int n; 顶点数int e; 边数; 算法6.2是在邻接表存储结构ALGraph上对图的构造的实现算法。 注意：通常头结点以顺序结构存储，表结点以链式结构存储。6.3 图的遍历 设图G中的所有顶点均未被访问过，在图G中任选一个顶点v为初始出发点，则深度优先搜索描述如下：首先访问初始出发点v，并将其标记为已访问过，然后依次从v出发遍历v的

13、每个邻接点w。若邻接点w未曾访问过，则以w为新的出发点继续进行深度优先搜索，直至图中所有和出发点v有路径相通的顶点均已被访问过为止。若此时图中仍有未访问的顶点，则另选一个未访问的顶点作为新的出发点重复上述过程，直至图中所有顶点均已被访问为止。6.3.1 深度优先搜索 以下图(a)为例来说明深度优先搜索的过程。遍历过程如图(b)所示。 假定A是初始出发点，首先访问A。 因A有两个邻接点B，C均未被访问，选择B作为新的出发点。 找B的未访问过的邻接点，与B邻接的有A，D，E，A已被访问过，D，E未被访问，选择D作为新的出发点。 重复上述搜索过程依次访问H，E。 访问E之后，由于与E相邻的顶点均被访

14、问，搜索退回到H。 由于H，D，B都没有未被访问的邻接点，所以搜索过程连续地从H退回到D，再退回到B，最后退回到A。 选择A未被访问过的邻接点C，继续往下搜索，依次访问C，F，G，I，从而遍历了图中全部顶点。 由此，得到顶点的访问序列为：ABDHECFGI。 深度优先遍历类似树的先序遍历，遍历方法的特点 是尽可能先对纵深方向进行搜索。 整个图的深度优先搜索如算法6.3和算法6.4所示。 假设图G中的所有顶点均未被访问过，在图G中任选一个顶点v为初始出发点，则广度优先搜索描述如下： 首先访问初始出发点v，并将其标记为已访问过，然后依次从v出发遍历v的每个邻接点w1，w2，wn，然后再依次访问与邻

15、接点w1，w2，wn邻接的所有未曾访问过的顶点。以此类推，直至图中所有和出发点v有路径相通的顶点都已访问完为止。若G是连通图，则遍历完成；否则，在图G中另选一个未访问的顶点作为新的出发点继续上述搜索过程，直至G中所有顶点均已被访问完为止。6.3.2 广度优先搜索 以下图(a)所示的图为例来说明广度优先搜索的过程。遍历过程如图(b)所示。 假定A是初始出发点，首先访问A。 因A有两个邻接点B，C均未被访问，先选择B作为新的出发点。 访问B之后，再访问C。 因B的邻接点有A，D，E，其中A已被访问过，而D，E未被访问，先访问D之后，再访问E。 然后访问C的未被访问邻接点F，G。 最后访问D的未曾访

16、问过的邻接点H和G的未曾访问过的邻接点I，从而遍历了图中全部顶点。 由此，得到顶点的访问序列为：ABCDEFGHI。 广度优先搜索类似于树的按层序遍历，采用的搜索方法的特点是尽可能先对横向进行搜索。 整个图的广度优先搜索如算法6.5和算法6.6所示。 图的连通分量是指无向图中的极大连通子图，而极大连通子图就是指无向图所包含的最多顶点数的连通子图。 对无向图进行遍历时，对于一个连通图，仅需从图中任一顶点出发，调用DFS或BFS一次便可访问完图中所有顶点。6.3.3 图的连通分量计算 对于一个非连通图，则需要多次调用DFS或BFS，每一次都要得到一个连通分量，调用DFS或BFS的次数恰好是连通分量

17、的个数。 用邻接表对如下图(a)所示的无向非连通图进行存储后，调用深度优先搜索算法，需要3次调用DFS，从而能够得到图的连通分量是3，其连通子图见图(b)。图(a)图(b)6.4 图的应用 生成树（tree）各边的权值总和称为该树的权，记作：W(T)=W(u,v)，W(u,v)表示边(u,v)的权。 权值最小的生成树称为图的最小生成树（minimum cost spanning tree）,简记为MST。6.4.1 最小生成树 最小生成树的性质： 设G=(V，E)是一个连通图，U是顶点集V的一个真子集。若(u,v)是具有最小权值的一条边(uU,vV-U)，则一定存在G的一棵最小生成树包括此边。

18、 构造最小生成树的算法有多种，主要有两种： 普里姆（Prim）算法 克鲁斯卡尔（Kruskal）算法 它们都是利用MST的性质构造最小生成树的。 普里姆算法：假设G=(V，E)是赋权连通图，T是G上最小生成树边的集合。算法从U=u0(u0V),T=开始，重复执行下述操作：在所有uU，vV-U的边(u，v)E中找一条权值最小的边(u0，v0)并入集合T，同时v0并入U，直至U=V为止。最后得到最小生成树MST=(V，T)，且T中必有n-1条边。 【例6-6】如下图所示为赋权图按普里姆算法构造一棵最小生成树的过程。 普里姆算法如算法6.7所示。 对于【例6-6】中的赋权图，利用算法6.7将输出最小

19、生成树的5条边，它们分别为(A,C)、(C,F)、(F,D)、(C,B)、(B,E)。 注意：普里姆算法的时间复杂度是O(n2)与图中的边数无关，适用于求稠密图的最小生成树。 克鲁斯卡尔算法 ：假设G=（V，E）是赋权连通图，令最小生成树的初始状态T只有n个顶点而无任何一条边，即图中每个顶点自成一个连通分量。在E中选择权值最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条权值最小的边。重复上述操作，直至T中所有顶点都在同一连通分量上为止。 【例6-7】如下图所示为赋权连通图按克鲁斯卡尔算法构造一棵最小生成树的过程。 注意：克鲁斯卡尔算法的时间复杂度

20、是O(eloge)，与图中的边数有关，适用于求稀疏图的最小生成树。 图的最短路径问题分为两类：求从某个源点到其余各顶点的最短路径；求每一对顶点之间的最短路径。 单源点的最短路径问题：给定带权有向图G和源点v，求从v到G中其余顶点的最短路径。算法的基本思想：按最短路径长度递增的次序求得各条路径。6.4.2 最短路径 其中，从源点到顶点vi的最短路径是所有最短路径中长度最短者。 长度最短的最短路径的特点：在这条路径上，必定只含一条弧，并且这条弧的权值最小。 下一条路径长度次短的最短路径的特点：它只可能有两种情况，或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧

21、组成)。 再下一条路径长度次短的最短路径的特点：它可能有两种情况，或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。 其余最短路径的特点：它或者是直接从源点到该点(只含一条弧)； 或者是从源点经过已求得最短路径的顶点，再到达该顶点。 使用最短路径的迪杰斯特拉算法求这些路径。 算法描述如下： 设置辅助数组D，其中每个分量Dk表示当前所求得的从源点到其余各顶点 k 的最短路径。Dk=arcsv0k，v0和k之间存在弧；Dk=，v0和k之间不存在弧，其中的最小值即为最短路径的长度。一般情况下，Dk = 或者+ 。（1）在所有从源点出发的弧中选取一条权值最

22、小的弧，即为第一条最短路径。 （2）修改其他各顶点的Dk值。（3）重复操作（1）、（2）步骤共n-1次。由此求得从源点到图上其余各顶点的最短路径是依路径长度递增的序列。 迪杰斯特拉算法如算法6.8所示。 偏序指集合中部分成员之间可比较，全序指集合中所有成员之间均可比较。 下图所示的两个有向图，图中弧表示vw，(a)表示偏序关系，图(b)表示全序关系，图(a)中的顶点B与顶点C无法比较。 6.4.3 拓扑排序 “拓扑排序”： 对有向图进行如下操作：按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系，由此所得顶点的线性序列称之为拓

23、扑有序序列。 例如，上图(a)所示的有向图的拓扑有序序列为：A B C D 或 A C B D。 对于下图所示的有向图，则不能求得它的拓扑有序序列。因为图中存在一个回路 B, C, D。 可用拓扑排序对有向图是否存在回路进行检查。解决的方法如下： （1）从有向图中选取一个没有前驱的顶点，并输出之。（2）从有向图中删去此顶点以及所有以它为尾的弧。 重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况说明有向图中存在环。 根据上述方法，下图所示为图拓扑有序序列的产生步骤。 图(a)原图，图(b)输出A，图(c)输出C，图(d)输出B，图(e)输出D，图(f)输出E。 得到该有向图的拓扑有序序列为：ACBDEF。（注：结果不唯一。） 拓扑排序的算法如算法6.9所示。6.5 实例解析与编程实现【例6-8】已知如下图所示的有向图，请给出该图的：(1) 每个顶点的出度和入度。(2) 邻接矩阵。(3) 邻接表。(4) 逆邻接表。 解：(1) 每个顶点的出度和