图的基本概念及拓扑排序ppt课件

1、图的基本概念遍历以及拓扑排序算法什么是图？o 什么是图?可用一句话概括，即：图是用点和线来刻划离散事物集合中的每对事物间以某种方式相联系的数学模型.因为它显得太抽象，不便于理解，所以有必要给出另外的回答. 1 1 图的基本术语图的基本术语图：记为图：记为 G G( V, E ) ( V, E ) 其中：其中：V V 是是G G的顶点集合，是有穷非空集；的顶点集合，是有穷非空集；E E 是是G G的边集合，是有穷集。的边集合，是有穷集。有向图：有向图：无向图：无向图：图图G G中的每条边都是有方向的；中的每条边都是有方向的；图图G G中的每条边都是无方向的；中的每条边都是无方向的；V=verte

2、x E=edge例：判断下列例：判断下列4种图形各属什么类型？种图形各属什么类型？无向无向无向图无向图(树树)有向图有向图有向有向完全图完全图完全图完全图稀疏图：稠密图： 设有两个图设有两个图 G(V, E) 和和 G(V, E)。假设。假设 V V 且且 E E, 则称则称 图图G 是是 图图G 的子图。的子图。子 图：边较少的图。通常边数边较少的图。通常边数n2边很多的图。无向图中，边数接近边很多的图。无向图中，边数接近n(n-1)/2 ； 有向图中，边数接近有向图中，边数接近n(n-1) 补补 图：图： 定义定义1：设图：设图G1=和图和图G2=是图是图G=的子的子图图.如果如果E2=E

3、- E1且且G2=，则称图，则称图G2是相对于图是相对于图G的子图的子图G1的补图的补图.定义定义2：给定图：给定图G=，若存在图，若存在图G1=，并且，并且E1E=和图和图是完全图，则是完全图，则G1称为相对于完全图的称为相对于完全图的G的补图，简称的补图，简称G1是是G的补图的补图. 带权图：带权图：即边上带权的图。其中权是指每条边可以标上即边上带权的图。其中权是指每条边可以标上具有某种含义的数值即与边相关的数）。具有某种含义的数值即与边相关的数）。带权图网网 络：络： 途径：途径： 在图在图 G(V, E) 中中, 若从顶点若从顶点 vi 出发出发, 沿一些边沿一些边经过一些顶点经过一些

4、顶点 vp1, vp2, , vpm，到达顶点，到达顶点vj。则称顶。则称顶点序列点序列 ( vi vp1 vp2 . vpm vj ) 为从顶点为从顶点vi 到顶点到顶点 vj 的的路径。它经过的边路径。它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj)应当是属于应当是属于E的边。的边。 路径长度：路径长度：连通图：连通图：强连通图：强连通图：生成树：生成树：邻接点： 顶点顶点v的度是与它相关联的边的条数。记作的度是与它相关联的边的条数。记作TD(v)。 在有向图中在有向图中, 顶点的度等于该顶点的入度与出度之和。顶点的度等于该顶点的入度与出度之和。 顶点顶点 v 的

5、入度是以的入度是以 v 为终点的有向边的条数为终点的有向边的条数, 记作记作 ID(v); 顶点顶点 v 的出度是以的出度是以 v 为始点的有向边的条数为始点的有向边的条数, 记作记作 OD(v)。假设假设 (u, v) 是是 E(G) 中的一条边，则称中的一条边，则称 u 与与 v 互为邻接顶点互为邻接顶点度、入度和出度：最小生成树：最小生成树：最小生成树算法：Prim算法和算法和kruskal算法算法简单路径：路径上各顶点路径上各顶点 v1,v2,.,vm v1,v2,.,vm 均不互相重复。均不互相重复。回 路：例：例：若路径上第一个顶点若路径上第一个顶点 v1 v1 与最后一个顶点与最

6、后一个顶点vm vm 重合，重合，则称这样的路径为回路或环。则称这样的路径为回路或环。图的数学表示o 点: 用整数0, 1, 2, , V-1表示o 边: 用无序数对(u, v)表示, 或者表示成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

7、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 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行含义：以结点行含义：以结点vivi为起点的边为起点的边( (即出边）；即出边）； 第第i i列含义：以结点列含义：以结点vivi为终点的弧为终点的

8、弧( (即入边）。即入边）。顶点表：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 特别讨论特别讨论 ：网即有权图的邻接矩阵：网即有权图的邻接矩阵定义为：定义为： 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; 阐明： adjlis

9、tij 若无权图无重边则直接用0 1表示I j两点 是否直接邻接 若无权图有重边则直接用0 1.表示是I j两点之间边的个数 若有权图则用来表示I j两点之间的距离 或者其他权值 二、邻接表链式表示法二、邻接表链式表示法adjvexnextarc权权值值datafirstarc邻接点域，表邻接点域，表示示vi一个邻接一个邻接点的位置点的位置链域，指向链域，指向vi下一个边下一个边或弧的结点或弧的结点数据域，存数据域，存储顶点储顶点vi 的的序号序号链域，指向链域，指向单链表的第单链表的第一个结点一个结点邻接表的缺点：邻接表的缺点：邻接表的优点：邻接表的优点：空间效率高；容易寻找顶点的邻接点；空

10、间效率高；容易寻找顶点的邻接点；一般用于稀疏图一般用于稀疏图判断两顶点间是否有边或弧，需搜索两判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。结点对应的单链表，没有邻接矩阵方便。邻接表 邻接矩阵存储比较邻接矩阵的优点：邻接矩阵的优点：判断两顶点间是否有边或弧，可以直接判断判断两顶点间是否有边或弧，可以直接判断速度很快速度很快 一般用于存储稠密图一般用于存储稠密图邻接矩阵的缺点：邻接矩阵的缺点：存储空间大存储空间大 会影响算法的空间效率会影响算法的空间效率 甚甚至时间效率至时间效率讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？1. 1. 联络：

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

12、稠密图的存储e e接近接近n(n-n(n-1)/2)1)/2)；而邻接表多用于稀疏图的存储；而邻接表多用于稀疏图的存储en2)e1. 容易证明对于任意距离值x, di=x的点一定是正确的, 而且白色点(没有计算出距离的点)的距离一定至少为x+1o 更进一步, 根据每个点的parent值, 可以计算出它到s的一条最短路Bfs算法中路径的打印Print-Path(G,s,v) if(v=s) then print s else if v=NIL then print “no path from ”sto” vexits” else Print-path(G,s, v) print v机器人问题机器

13、人问题o Dr.Kong是设计了一个可以前进或者后退的机器人，该机器人在每一个位置i会得到一个o移动的步数指令Kii=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组测试数据

14、0M=8）o 接下来每组有两行数据o 头一行：N A B1=N=50,1=A,B=N）o 下一行：K1 K2Kn0=Kinab;ofor (int i=1;itemp;o if(i+temp=1)o argsii-temp=true;oooda=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);

15、o o oocoutdbendl;二、深度优先遍历二、深度优先遍历(DFS)基本思想：基本思想：仿树的先序遍历过程。仿树的先序遍历过程。Depth_First Searchv1v2v3v8v7v6v4v5起点起点起点起点遍历步骤遍历步骤深度优先搜索遍历步骤：深度优先搜索遍历步骤：详细归纳：详细归纳：在访问图中某一起始顶点在访问图中某一起始顶点 v 后，由后，由 v 出发，访问它的任一邻接出发，访问它的任一邻接顶点顶点 w1；再从再从 w1 出发，访问与出发，访问与 w1邻接但还未被访问过的顶点邻接但还未被访问过的顶点 w2；然后再从然后再从 w2 出发，进行类似的访问，出发，进行类似的访问，

16、如此进行下去，直至到达所有的邻接顶点都被访问过的顶点如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。它没有被访问的邻接顶点。 如果有，则访问此顶点，之后再从此顶点出发，进行与前述如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；类似的访问； 如果没有，就再退回一步进行搜索。重复上述过程，直到连如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。通图中所有顶点都被访问过为止。简单归纳：简单归纳： 访问

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

18、算法o 初始化: time为0, 所有点为白色, dfs森林为空o 对每个白色点u执行一次DFS-VISIT(u)o 时间复杂度为O(n+m)DFS树的性质o 括号结构性质o 对于任意结点对(u, v), 考虑区间du, fu和dv, fv, 以下三个性质恰有一个成立:o 完全分离o u的区间完全包含在v的区间内, 则在dfs树上u是v的后代o v的区间完全包含在u的区间内, 则在dfs树上v是u的后代o 三个条件非常直观DFS树的性质o 定理1(嵌套区间定理): 在DFS森林中v是u的后代当且仅当dudvfv=0; w=NextAdjVex(G,u,w)o if (!visitedw) Pu

19、sh(G, w)/将没访问的邻接点压栈 o o DestroyStack(S); /释放栈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 =

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

21、明是非连通图对于有向图：以后在学习的过程中会做深入的探讨深搜示例：/JudgeOnline/problem?id=2386题目大意：如左图所示 一块矩形地 其中W代表的是水.代表的是陆地 其中我们认为每个方格和它的 八个方向全部是邻接的问其中有多少池塘题目分析 访问一次水方格，我们可以将其8个方向的水方格全部访问，这样我们对一个水方格进行深搜就可以将与其之间有路径的所有点全部访问。既是可以访问一个连通分支也就是一个湖）。搜索的次数就是湖的个数示例代码：o#include ousing namespace std;oint a101101;/记录矩形方格对应的是水还是陆地o

22、int sum,n,m; /sum记录湖的个数n 矩形地的行数m矩形地的列数oint flag101101;/标记每个方格是否已经被访问过o/定义的个方向oint d82=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;

23、/标记当前结点已经访问ofor(int i=0;inm)o omemset(flag,0,sizeof(flag); /全部方格标记为没有访问omemset(a,0,sizeof(a); /方格全部标记为陆地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

24、oreturn 0; oo对于无向图的连通分支数的判断既可以用广度优先搜索 也可以用深度优先搜索o大家一定要试着写一下此题的广度优先搜索代码推荐题目搜索经典题目 迷宫求解：用一个矩形表示地图，其中矩形由方格组成，每个方格为路或者是墙。给你一个起点位置和一个终止位置，问你是否能从 开头位置到达终点位置，我们认为起始位置和终点位置是不重合的，并且我们只能走直路，不可以走斜路 。我们保证起点和终点都是空位置。要求你求一下这条路径是否存在，存在的话。求出路径的长度 输入说明 ：第一行 m n 代表矩形是m行n列的 p q r s ，（p，q开始位置，（r，s） 目标位置 接下来的m行 每行共n个01代

25、码，其中0代表是通路，1代表是墙。 输出说明：有路径输出yes并输出最短路径各一行，没有路径直接输出no 占一行 示例输入：2 2 0 0 1 1 0 1 0 0 示例输出：yes 2 思路深搜只能求是否有通路，广搜是否有通路和最短路径都可以求出来/showproblem.php?pid=1253/showproblem.php?pid=1372/showproblem.php?pid=1198/showproblem.php?pid=1232老队员可以自己在网上搜一些题目做 拓扑排序问题学生课程学习工程图

26、学生课程学习工程图o 检测有向环的一种方法是对检测有向环的一种方法是对AOV网络构造它的拓网络构造它的拓扑有序序列。即将各个顶点扑有序序列。即将各个顶点 (代表各个活动代表各个活动)排列排列成一个线性有序的序列，使得成一个线性有序的序列，使得AOV网络中所有应网络中所有应存在的前驱和后继关系都能得到满足。存在的前驱和后继关系都能得到满足。 o 这种构造这种构造AOV网络全部顶点的拓扑有序序列的运网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。算就叫做拓扑排序。o 如果通过拓扑排序能将如果通过拓扑排序能将AOV网络的所有顶点都排网络的所有顶点都排入一个拓扑有序的序列中，则该入一个拓扑有序的序列中

27、，则该AOV网络中必定网络中必定不会出现有向环；相反，如果得不到满足要求的不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明拓扑有序序列，则说明AOV网络中存在有向环，网络中存在有向环，此此AOV网络所代表的工程是不可行的。网络所代表的工程是不可行的。o 例如，对学生选课工程图进行拓扑排序，得到的例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为拓扑有序序列为o C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7或或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6o 可以用有向图表示一个工程。在这种有向图中，可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边用顶点表示活动，用有向边表示活动。表示活动。Vi 必须先于活动必须先于活动Vj 进展。这种有向图叫做顶点进展。这种有向图叫做顶点表示活动的表示活动的AOV网络网络(Activity On Vertices)。 o 在在AOV网络中，如果活动网络中，如果活动Vi 必须在活动必须在活动Vj 之前之前进行，则存在有向边进行，则存在有向边， AOV网络中不能网络中不能出现有向回路，即有向环。在出现有向回路，即有向环。在AOV网络中如果出网络中如果出现了