最新图的基本概念及拓扑排序PPT课件.ppt

《最新图的基本概念及拓扑排序PPT课件.ppt》由会员分享，可在线阅读，更多相关《最新图的基本概念及拓扑排序PPT课件.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图的基本概念及拓扑排序图的基本概念及拓扑排序什么是图？o 什么是图?可用一句话概括，即：图是用点和线来刻划离散事物集合中的每对事物间以某种方式相联系的数学模型.因为它显得太抽象，不便于理解，所以有必要给出另外的回答. 简单路径：路径上各顶点路径上各顶点 v v1 1,v,v2 2,.,v,.,vm m 均不互相重复。均不互相重复。回 路：例：例：若路径上第一个顶点若路径上第一个顶点 v v1 1 与最后一个顶点与最后一个顶点v vm m 重合，重合，则称这样的路径为则称这样的路径为回路或环回路或环。图的数学表示o 点: 用整数0, 1, 2, , V-1表示o 边: 用无序数对(u, v)表示

2、, 或者表示成u-v7.2 7.2 图的存储结构图的存储结构重点介绍：重点介绍：o 主要有下面四种方法：o 邻接矩阵o 邻接表o 十字链表o 多重链表一、邻接矩阵（数组）表示法一、邻接矩阵（数组）表示法 , ),( , , .否否则则或或者者如如果果01AEjiEjijiEdge1235v4 4AA.Edge =（ 1 2 3 4 5 ）123450 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0

3、10 1 1 1 0例例2 ：有向图的邻接矩阵有向图的邻接矩阵v1v2v3v4邻接矩阵：A.Edge =( v1 v2 v3 v4 )v1v2v3v40 0 0 00 0 0 0 0 0 0 0 0 0 0 0 注：注：在有向图的邻接矩阵中，在有向图的邻接矩阵中， 第第i i行含义：以结点行含义：以结点v vi i为起点的边为起点的边( (即出边）；即出边）； 第第i i列含义：以结点列含义：以结点v vi i为终点的弧为终点的弧( (即入边）。即入边）。顶点表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 特别讨论

4、特别讨论 ：网（即有权图）的邻接矩阵网（即有权图）的邻接矩阵定义为：定义为： A.Edge i j =Wij 或（或（vi, vj）VR 无边（弧）无边（弧）v1v2v3v4Nv5v65489755613以有向网为例：以有向网为例：邻接矩阵：N.Edge =(1 2 3 4 5 6 )顶点表： 5 7 4 8 9 5 6 5 3 1 图的邻接矩阵表示示例int adjlistmax_vex_nummax_vex_num; 说明： adjlistij 若无权图无重边则直接用0 1表示I j两点 是否直接邻接 若无权图有重边则直接用0 1.表示是I j两点之间边的个数 若有权图则用来表示I j两点

5、之间的距离 或者其他权值 二、邻接表（链式）表示法二、邻接表（链式）表示法adjvexnextarc权权值值datafirstarc邻接点域，邻接点域，表表示示v vi i一个邻接一个邻接点的位置点的位置链域，链域，指向指向vivi下一个边下一个边或弧的结点或弧的结点数据域，存数据域，存储顶点储顶点vi 的的序号序号链域，链域，指向指向单链表的第单链表的第一个结点一个结点邻接表的邻接表的缺点：缺点：邻接表的优点：邻接表的优点：空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点；一般用于稀疏图一般用于稀疏图判断两顶点间是否有边或弧，需搜索两判断两顶点间是否有边或弧，需搜索两结点对

6、应的单链表，没有邻接矩阵方便。结点对应的单链表，没有邻接矩阵方便。邻接表 邻接矩阵存储比较邻接矩阵的优点：邻接矩阵的优点：判断两顶点间是否有边或弧，可以直接判断判断两顶点间是否有边或弧，可以直接判断速度很快速度很快 一般用于存储稠密图一般用于存储稠密图邻接矩阵的邻接矩阵的缺点：缺点：存储空间大存储空间大 会影响算法的空间效率会影响算法的空间效率 甚甚至时间效率至时间效率讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？1. 1. 联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结

7、点个数等于一行中非零元素的个数。2. 2. 区别：区别： 对于任一确定的无向图，邻接矩阵是唯一的（行列对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。与顶点编号无关）。 邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复而邻接表的空间复杂度为杂度为O(n+e)O(n+e)。3. 3. 用途：用途：邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e e接近接近n(n-n(n-1)/2)1)/2)；而邻接表多用于稀疏图的存储（；而邻接表多用于稀疏图的存储

8、（ene1. 容易证明对于任意距离值x, di=x的点一定是正确的, 而且白色点(没有计算出距离的点)的距离一定至少为x+1o 更进一步, 根据每个点的parent值, 可以计算出它到s的一条最短路Bfs算法中路径的打印Print-Path(G,s,v)o if(v=s)o then print so else if v=NILo then print “no path from ”s”to” v”exits”o else Print-path(G,s, v) print v机器人问题机器人问题o Dr.Kong是设计了一个可以前进或者后退的机器人，该机器人在每一个位置i会得到一个o移动的步数

9、指令Ki（i=1，2n），聪明的机器人会自己判断是要前进Ki步还是要后退Ki步。o 例如：给定指令序列（3，3，1，2，5），表示机器人在第一个位置时，可以前进3步到第4个位置，此时后退是不起作用的，出界：机器人在第2个位置时，可以前进3步到第5个位置，此时后退时不起作用的，出界：机器人在第3个位置的时，可以前进1步到第4个位置，也可以后退一步到第2个位置等等.o 你认为，对于给定的两个位置A，B，聪明的机器人从A位置到B位置至少需要判断几次？oinputo 第一行：M 表示以下有M组测试数据（0M=8）o 接下来每组有两行数据o 头一行：N A B（1=N=50,1=A,B=N）o 下一行：

10、K1 K2Kn（0=Kinab;ofor (int i=1;itemp;o if(i+temp=1)o argsii-temp=true;ooda=0;ovisiteda=true;oqueueq;o q.push(a);owhile(!q.empty()oo int temp=q.front();o q.pop();ofor(int i=0;i=n;i+)oo if(argstempi&!visitedi)o odi=dtemp+1;ovisitedi=true;o q.push(i);o o oocoutdbendl;二、深度优先遍历二、深度优先遍历(DFS)基本思想：基本思想：仿树的先序

11、遍历过程。仿树的先序遍历过程。Depth_First Searchv1v2v3v8v7v6v4v5起点起点起点起点遍历步骤遍历步骤深度优先搜索（遍历）步骤：深度优先搜索（遍历）步骤：详细归纳：详细归纳：E在访问图中某一起始顶点在访问图中某一起始顶点 v 后，由后，由 v 出发，访问出发，访问它的任一邻接它的任一邻接顶点顶点 w1；E再从再从 w1 出发，访问出发，访问与与 w1邻接邻接但还但还未被访问未被访问过的顶点过的顶点 w2；E然后再从然后再从 w2 出发，进行类似的访问，出发，进行类似的访问， E如此进行下去，直至到达所有的邻接顶点都被访问过的顶点如此进行下去，直至到达所有的邻接顶点都

12、被访问过的顶点 u 为止。为止。E接着，退回一步，接着，退回一步，退到前一次刚访问过的顶点退到前一次刚访问过的顶点，看是否还有，看是否还有其它没有被访问的邻接顶点。其它没有被访问的邻接顶点。 如果有，如果有，则访问此顶点，之后再从此顶点出发，进行与前述则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；类似的访问； 如果没有，如果没有，就就再退回一步再退回一步进行搜索。重复上述过程，直到连进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。通图中所有顶点都被访问过为止。简单归纳：简单归纳： 访问起始点访问起始点 v; 若若v的第的第1个邻接点没访问过，深度遍历此邻接点；个邻接点没访

13、问过，深度遍历此邻接点；若当前邻接点已访问过，再找若当前邻接点已访问过，再找v的第的第2个邻接点重新遍历。个邻接点重新遍历。基本算法o 新发现的结点先扩展o 得到的可能不是一棵树而是森林, 即深度优先森林(Depth-first forest)o 特别之处: 引入时间戳(timestamp)n 发现时间dv: 变灰的时间n 结束时间fv: 变黑的时间n 1=dv fv = 2|V|o 初始化: time为0, 所有点为白色, dfs森林为空o 对每个白色点u执行一次DFS-VISIT(u)DFS-VISIT算法o 初始化: time为0, 所有点为白色, dfs森林为空o 对每个白色点u执行一

14、次DFS-VISIT(u)o 时间复杂度为O(n+m)DFS树的性质o 括号结构性质o 对于任意结点对(u, v), 考虑区间du, fu和dv, fv, 以下三个性质恰有一个成立:n 完全分离n u的区间完全包含在v的区间内, 则在dfs树上u是v的后代n v的区间完全包含在u的区间内, 则在dfs树上v是u的后代o 三个条件非常直观DFS树的性质o 定理1(嵌套区间定理): 在DFS森林中v是u的后代当且仅当dudvfv=0; w=NextAdjVex(G,u,w)o if (!visitedw) Push(G, w)/将没访问的邻接点压栈 o o DestroyStack(S); /释放

15、栈o / DFS数据结构书上的深度优先搜索算法obool visitedmax;/访问标志数组oStatus (*VisitFunc)(int v);/函数变量ovoid DESTraverse(Graph G,status(*visit)(int v) o /对图G进行深度优先搜索（图G连通与否都可以）o visitFunc = visit;/使用全局变量Visitfunc，使DFS函数不必设置函数指针o /访问标志数组初始化为全部没有访问o for(v=0,vG.vecnum;+v) visitdv = false;o for(v=0;v=0;w=nextAdjvex(G,v,w)o if

16、(!visitedw) DFS(G,w);/对v的尚未访问过的邻接点w递归调用DFSo如果是连通图此处的DFS只会被执行一次如果是非连通图此处DFS执行的次数就是连通分支数图的连通性问题o 对于无向图o 若是连通图则从图中任意顶点出发进行广搜或者深搜便可以访问到图中的任意顶点o 非连通图则需要多次调用DFS才可全部访问 每次DFS可以访问一个连通分量中的所有顶点 调用DFS的次数为图的连通分支数o 另外采用并查集也可以解决这个问题，并且空间效率比较低。最后若能归并成一个几何则说明为连通的，若最后是多个集合则说明是非连通图对于有向图：l以后在学习的过程中会做深入的探讨深搜示例：http:/ 一块

17、矩形地 其中W代表的是水.代表的是陆地 其中我们认为每个方格和它的 八个方向全部是邻接的问其中有多少池塘题目分析 访问一次水方格，我们可以将其8个方向的水方格全部访问，这样我们对一个水方格进行深搜就可以将与其之间有路径的所有点全部访问。既是可以访问一个连通分支（也就是一个湖）。搜索的次数就是湖的个数示例代码：o#include ousing namespace std;oint a101101;/记录矩形方格对应的是水还是陆地oint sum,n,m; /sum记录湖的个数n 矩形地的行数m矩形地的列数oint flag101101;/标记每个方格是否已经被访问过o/定义的个方向oint d8

18、2=1,0,1,1,0,1,-1,1,-1,0,-1,-1,0,-1,1,-1;o/检查x y是否出界obool check(int x,int y)o oif(x0&x0&y=m) oreturn 1; oreturn 0; oo/以一个方格开始深度优先搜索ovoid dfs(int x,int y)o oif(flagxy|!axy)/点已经访问或者是陆地则停止访问 oreturn ; oflagxy=1; /标记当前结点已经访问ofor(int i=0;inm)o omemset(flag,0,sizeof(flag); /全部方格标记为没有访问omemset(a,0,sizeof(a)

19、; /方格全部标记为陆地osum=0; /初始化湖的个数为ofor(i=1;i=n;i+) ofor(j=1;jc; oif(c=W)aij=1; /是水的方格标记为水 o ofor(i=1;i=n;i+) ofor(j=1;j=m;j+) /对是水且未被访问过的方格进行深搜oif(aij&!flagij) /每次访问访问一个连通分支即一个湖odfs(i,j),sum+; ocoutsumendl; o oreturn 0; oo对于无向图的连通分支数的判断既可以用广度优先搜索 也可以用深度优先搜索o大家一定要试着写一下此题的广度优先搜索代码推荐题目搜索经典题目 迷宫求解：用一个矩形表示地图，

20、其中矩形由方格组成，每个方格为路或者是墙。给你一个起点位置和一个终止位置，问你是否能从 开头位置到达终点位置，我们认为起始位置和终点位置是不重合的，并且我们只能走直路，不可以走斜路 。我们保证起点和终点都是空位置。要求你求一下这条路径是否存在，存在的话。求出路径的长度 输入说明 ：第一行 m n 代表矩形是m行n列的 p q r s ，（p，q）开始位置，（r，s） 目标位置 接下来的m行 每行共n个01代码，其中0代表是通路，1代表是墙。 输出说明：有路径输出yes并输出最短路径各一行，没有路径直接输出no 占一行 示例输入：2 2 0 0 1 1 0 1 0 0 示例输出：yes 2 思路

21、深搜只能求是否有通路，广搜是否有通路和最短路径都可以求出来深搜只能求是否有通路，广搜是否有通路和最短路径都可以求出来ohttp:/ 拓扑排序问题学生课程学习工程图学生课程学习工程图o 检测有向环的一种方法是对检测有向环的一种方法是对AOV网络构造它的拓网络构造它的拓扑有序序列。即将各个顶点扑有序序列。即将各个顶点 (代表各个活动代表各个活动)排列排列成一个线性有序的序列，使得成一个线性有序的序列，使得AOV网络中所有应网络中所有应存在的前驱和后继关系都能得到满足。存在的前驱和后继关系都能得到满足。 o 这种构造这种构造AOV网络全部顶点的拓扑有序序列的运网络全部顶点的拓扑有序序列的运算就叫做拓

22、扑排序。算就叫做拓扑排序。o 如果通过拓扑排序能将如果通过拓扑排序能将AOV网络的所有顶点都排网络的所有顶点都排入一个拓扑有序的序列中，则该入一个拓扑有序的序列中，则该AOV网络中必定网络中必定不会出现有向环；相反，如果得不到满足要求的不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明拓扑有序序列，则说明AOV网络中存在有向环，网络中存在有向环，此此AOV网络所代表的工程是不可行的。网络所代表的工程是不可行的。o 例如，对学生选课工程图进行拓扑排序，得到的例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为拓扑有序序列为o C1 , C2 , C3 , C4 , C5 , C6

23、 , C8 , C9 , C7或或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6o 可以用可以用有向图有向图表示一个工程。在这种有向图中，表示一个工程。在这种有向图中，用顶点表示活动用顶点表示活动，用有向边用有向边表示活动。表示活动。Vi 必须先于活动必须先于活动Vj 进行。这种有向图叫做顶点表示进行。这种有向图叫做顶点表示活动的活动的AOV网络网络(Activity On Vertices)。 o 在在AOV网络中，如果活动网络中，如果活动Vi 必须在活动必须在活动Vj 之前进之前进行，则存在有向边行，则存在有向边， AOV网络中不能出网络中不能出现有

24、向回路，即有向环。在现有向回路，即有向环。在AOV网络中如果出现网络中如果出现了有向环，则意味着某项活动应以自己作为先决了有向环，则意味着某项活动应以自己作为先决条件。条件。o 因此，对给定的因此，对给定的AOV网络，必须先判断它是否存网络，必须先判断它是否存在有向环。在有向环。进行拓扑排序的方法 输入输入AOV网络。令网络。令 n 为顶点个数。为顶点个数。 在在AOV网络中选一个没有直接前驱的顶点网络中选一个没有直接前驱的顶点, 并输出之并输出之; 从图中删去该顶点从图中删去该顶点, 同时删去所有它发出同时删去所有它发出的有向边的有向边; 重复以上重复以上 、 步步, 直到直到n 全部顶点均

25、已输出，拓扑有序序列形成，拓扑全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或排序完成；或n 图中还有未输出的顶点，但已跳出处理循环。图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。网络中必定存在有向环。拓扑排序的过程拓扑排序算法obool TopLogicalSort(Graph gf)oo SqStack s;o FindInDegree(gf);/求出各点的入度求出各点的入度o InitStack(s);o for

26、(int i = 0; i gf.vexnum; +i)o if(!gf.degreei) Push(s,i); /0入度顶点全部入栈入度顶点全部入栈o count = 0; /记录已经输出顶点的个数记录已经输出顶点的个数o while(!IsStackEmpty(s)o o Pop(s,i);o couti“ ”gf.verticesi.data nextarc)o o -gf.degreep-adjvex;o if(!gf.degreep-adjvex)Push(s,p-adjvex);o o o o if(count gf.vexnum ) return false; /未访问到所有顶点说明有回路未访问到所有顶点说明有回路o return true;oo 本次讲课的内容在算法导论322-336页o 哪里不懂的可以仔细的看一下。