2018图的存储与遍历及拓扑排序

1、图的存储遍历及拓扑排序,李云军,引例,有n个岛屿，给出他们的坐标， 任意两个岛屿间可以铺设一条通信电缆， 如果需要实现任意两个岛屿间都能 直接或间接通讯，求最少需要铺设的 电缆长度是多少？,某大学计算机专业的必修课及其先修课程如下表所示：,请给出一种合理的课程安排方案,图的相关概念,如果数据元素集合中的各元素之间存在任意的关系，则此数据结构称为图。如果将数据元素抽象为顶点，元素之间的关系用边表示，则图亦可以表示为G=（V，E），其中V是顶点的有穷（非空）集合，E为边的集合。,1、图的分类：无向图、有向图、带权图,无向图：边集E（G）中为无向边。,有向图：边集E（G）中为有向边。,带权图 ：边上

2、带有权的图。也称为网。（有向带权图、无向带权图）,2、顶点的度、入度、出度,顶点的度：与该顶点相关联的边的数目，有奇点、偶点之分。,对于有向图：有入度和出度之分,入度：该顶点的入边的数目。 出度：该顶点的出边的数目。,2,提问2：有向图中所有顶点的入度之和是(大于、等于、小于)所有顶点的出度之和；,提问3：任意一个无向图一定有（偶数、奇数）个奇点；,完全图：若是无向图中，则每两个顶点之间都存在着一条边；若是有向图，则每两个顶点之间都存在着方向相反的两条边。,3、完全图、稠密图、稀疏图,稠密图：当一个图的边数接近完全图时。,稀疏图：当一个图的边数远远少于完全图时。,n*(n-1)/2,n*(n-

3、1),路径：对于图G=（V，E），对于顶点a、b，如果存在一些顶点序列x1=a,x2,xk=b(k1)，且（xi,xi+1）E，i=1,2k-1，则称顶点序列x1,x2,xk为顶点a到顶点b的一条路径，而路径上边的数目（即k-1）称为该路径的长度。并称顶点集合x1,x2,xk为一个连通集。,简单路径：如果一条路径上的顶点除了起点和终点可以相同外，其它顶点均不相同，则称此路径为一条简单路径；起点和终点相同的简单路径称为回路（或环）。,4、子图,图G,图G,设两个图G=（V，E）和G=(V,E),若V是V的子集,且E是E的子集,则称G是G的子图。,5、路径和回路,路径和简单路径的举例：,左图123

4、是一条简单路径，长度为2， 而13413就不是简单路径； 右图121为一个回路。,连通图：如果一个无向图中，任意两个顶点之间都是连通的，则称该无向图为连通图。否则称为非连通图；左图为一个连通图。,连通分量：一个无向图的连通分支定义为该图的最大连通子图，左图的连通分量是它本身。,连通：在一个图中，如果从顶点U到顶点V有路径，则称U和V是连通的；,6、连通和连通分量,注意：任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。,强连通分量：一个有向图的强连通分量定义为该图的最大的强连通子图，右图含有两个强连通分量，一个是1和2构成的一个子图，一个是3独立构成的一个子图。,强连通图：在一个

5、有向图中，对于任意两个顶点U和V，都存在着一条从U到V的有向路径，同时也存在着一条从V到U的有向路径，则称该有向图为强连通图；右图不是一个强连通图。,7、强连通图和强连通分量,注意：强连通图只有一个强连通分量，即本身，非强连通图有多个强连通分量。,图的存储,图型结构的存储分为静态存储和动态存储。我们介绍下面三种：邻接矩阵、邻接表（用数组模拟），边集数组。,1、邻接矩阵,相邻矩阵是表示顶点间相邻关系的矩阵。若G=（V，E）是一个具有n个顶点的图，则G的相邻矩阵是如下定义的二维数组a，其规模为n*n,上图中的3个图对应的邻接矩阵分别如下： 0 1 1 1 0 1 1 5 8 3 G（A）= 1 0

6、 1 1 G（B）= 0 0 1 5 2 6 1 1 0 0 0 1 0 G（C）= 8 2 10 4 1 1 0 0 10 11 3 6 4 11 ,下面是建立图的邻接矩阵的参考程序段： int i,j,k,e,n;double g101101;double w; int main() int i,j; for (i = 1; i e; for (k = 1; k i j w; gij = w; /对于不带权的图gij=1 gji = w; /无向图的对称性,如果是有向图则不要有这句！ return 0; ,邻接矩阵存储的特点,1、占用的存储单元数只与顶点数有关而与边数无关，n*n的二维数组

7、。 2、方便度数的计算。 3、容易判断两点之间是否有边相连。 4、寻找一个点相连的所有边需要一个一到n的循环。,17,2、邻接表,头指针,邻接点指针,数组模拟邻接表方法一,int g101101; 寻找顶点i有边相连的点可以这样来做，gi0表示i发出的边的数量，gij表示i发出的第j条边是通向哪个顶点的。 for (int j = 1; j = gi0; j+) .gij. 这样就可以处理i发出的每条边，也就能找到顶点i有边相连的顶点。,数组模拟邻接表存储:大多数情况下只要用数组模拟即可。 参考程序段： #include using namespace std; const int maxn=

8、1001,maxm=100001; struct Edge int next; /下一条边的编号 int to; /这条边到达的点 edgemaxm; int headmaxn,num_edge,n,m,u,v; void add_edge(int from,int to) /加入一条从from到to的单向边 edge+num_edge.next=headfrom; edgenum_edge.to=to; headfrom=num_edge; ,5 6 0 4 1 0 1 2 2 0 2 3 3 4,headmaxn,edgemaxm,数组模拟邻接表方法二,int main() num_edg

9、e=0; scanf(%d %d, 两种方法各有用武之地，需按具体情况，具体选用。,headmaxn,edgemaxm,计算每个点的出度,邻接表存储特点,1、对于稀疏图，用链表实现的邻接表，可以节省内存。 2、可以快速找到与当前顶点相连的点。 3、判断两点是否相连不如邻接矩阵快速。,3、边集数组,边集数组：是利用一维数组存储图中所有边的一种图的表示方法。,起点,终点,权,无向带权图的边集数组表示法,图的遍历 从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。 遍历可以采取两种方法进行： 深度优先遍历 广度优先遍历,1、图的深度优先遍历,对下面两个图

10、分别进行深度优先遍历，写出遍历结果。注意：分别从a和V1出发。,左图从顶点a出发，进行深度优先遍历的结果为： a，b，c，d，e，g，f 右图从V1出发进行深度优先遍历的结果为： V1，V2，V4，V8，V5，V3，V6，V7,图的遍历分为深度优先遍历和广度（宽度）优先遍历两种方法。,为了避免重复访问某个顶点，可以设一个标志数组visi，未访问时值为0，访问一次后就改为1。,对下面两个图分别从a和V1出发进行广度优先遍历，写出遍历结果。,2、图的广度优先遍历,左图从顶点a出发，进行广度优先遍历的结果为： a，b，d，e，f，c，g 右图从V1出发进行广度优先遍历的结果为： V1，V2，V3，V

11、4，V5，V6，V7，V8,广度优先遍历的实现： 为避免重复访问，也需要一个状态数组 visn，用来存储各顶点的访问状态。如果 visi = 1，则表示顶点 i 已经访问过；如果 visi = 0，则表示顶点 i 还未访问过。初始时，各顶点的访问状态均为 0。 为了实现逐层访问， BFS 算法在实现时需要使用一个队列.,如果是非连通图，主程序做如下修改: int main() memset(vis,0,sizeof(vis); for (int i = 1; i = n; i+) if (visi=0) dfs(i); return 0; ,【数据规模】 100%的数据： n=10000； m

12、=100000。,分析 以人为图的顶点，相互认识的建立无向边，求无向图的连通分量数。,分析： 从网格中某个“”字符位置开始进行 DFS 搜索，可以搜索到跟该“”字符位置同属一块油田的所有“”字符位置。 遍历整个图，求图的连通分量。注意是8连通。,分析： 求男子所在位置能到达的黑色的连通块的大小。 从起点遍历图即可。,拓扑排序,AOV网 在日常生活中，一项大的工程可以看作是由若干个子工程（这些子工程称为“活动” ）组成的集合，这些子工程（活动）之间必定存在一些先后关系，即某些子工程（活动）必须在其它一些子工程（活动）完成之后才能开始，我们可以用有向图来形象地表示这些子工程（活动）之间的先后关系，

13、子工程（活动）为顶点，子工程（活动）之间的先后关系为有向边，这种有向图称为“顶点活动网络” ，又称“AOV网” 。,在AOV网中，有向边代表子工程（活动）的先后关系，我们把一条有向边起点的活动成为终点活动的前驱活动，同理终点的活动称为起点活动的后继活动。而只有当一个活动全部的前驱全部都完成之后，这个活动才能进行。例如在上图中，只有当工程1完成之后，工程2、3、4、5、6才能开始进行。只有当2、3、4全部完成之后，7才能开始进行。 一个AOV网必定是一个有向无环图，即不应该带有回路。否则，会出现先后关系的自相矛盾。,上图就是一个出现环产生自相矛盾的情况。4是1的前驱，想完成1，必须先完成4。3是

14、4的前驱，而2是3的前驱，1又是2的前驱。最后造成想完成1，必须先完成1本身，这显然出现了矛盾。,拓扑排序算法,拓扑排序算法，只适用于AOV网（有向无环图）。 把AOV网中的所有活动排成一个序列， 使得每个活动的所有前驱活动都排在该活动的前面，这个过程称为“拓扑排序”，所得到的活动序列称为“拓扑序列”。 一个AOV网的拓扑序列是不唯一的，例如下面的这张图，它的拓扑序列可以是：ABCDE，也可以是ACBDE，或是ADBCE。在下图所示的AOV网中，工程B和工程C显然可以同时进行，先后无所谓；但工程E却要等工程B、C、D都完成以后才能进行。,构造拓扑序列可以帮助我们合理安排一个工程的进度，由AOV

15、网构造拓扑序列具有很高的实际应用价值。,算法思想： 构造拓扑序列的拓扑排序算法思想很简单： 1）选择一个入度为0的顶点并输出 2）然后从AOV网中删除此顶点及以此顶点为起点的所有关联边； 3）重复上述两步，直到不存在入度为0的顶点为止。 4）若输出的顶点数小于AOV网中的顶点数，则输出“有回路信息”，否则输出的顶点序列就是一种拓扑序列 从第四步可以看出，拓扑排序可以用来判断一个有向图是否有环。只有有向无环图才存在拓扑序列。,算法实现： a) 数据结构：indgri: 顶点i的入度; stack : 栈 b) 初始化:top=0 (栈顶指针置零) c) 将初始状态所有入度为0的顶点压栈 d) I

16、=0 (计数器) e) while 栈非空(top0) i. 栈顶的顶点v出栈；top-1; 输出v；i+； ii. for v的每一个后继顶点u 1. indgru-; u的入度减1 2. if （u的入度变为0） 顶点u入栈 f) 算法结束 这个程序采用栈来找出入度为0的点，栈里的顶点，都是入度为0的点。,我们结合下图详细讲解：,简单&高效&实用的算法。上述实现方法复杂度O(V+E)。,【例5】重叠的图像-洛谷Luogu-2741 USACO4.4,. . . . .CCC. EEEEEE. . . .BBBB. .C.C. E.E. DDDDDD. . .B.B. .C.C. E.E.

17、D.D. . .B.B. .CCC. E.E. D.D. .AAAA .B.B. . E.E. D.D. .A.A .BBBB. . E.E. DDDDDD. .A.A . . E.E. . .AAAA . . EEEEEE. . . . .,.CCC. ECBCBB. DCBCDB. DCCC.B. D.B.ABAA D.BBBB.A DDDDAD.A E.AAAA EEEEEE.,现在，把这些图像按照 15 的编号从下到上重叠，第 1 张在最下面，第 5 张在最顶端。如果一张图像覆盖了另外一张图像，那么底下的图像的一部分就变得不可见了。我们得到右面的图像：,给出重叠后的图像图像，计算原矩形

18、图像从底部到顶端堆叠的顺序。 下面是这道题目的规则： 1）、矩形的边的宽度为 1 ，每条边的长度都不小于 3 。 2）、矩形的每条边中，至少有一部分是可见的。注意，一个角同时属于两条边。 3）、矩形用大写字母表示，并且每个矩形的表示符号都不相同。 【输入格式】 第一行 两个用空格分开的整数：图像高 H 和图像宽 W 。 第二行到第 H+1 行 H 行，每行 W 个字母。 【输出格式】 按照自底向上的顺序输出字母。如果有不止一种情况，按照字典顺序输出每一种情况（至少会有一种合法的顺序）。,【输入样例】 9 8 .CCC. ECBCBB. DCBCDB. DCCC.B. D.B.ABAA D.BBBB.A DDDDAD.A EAAAA EEEEEE.,【输出样例】 EDABC 【数据范围】 3 = H =30 3 = W = 30,分析,由于每