数据结构chapter92图的遍历,拓扑排序ppt课件

1、数数 据据 结结 构构 DATA STRUCTURE, DS DATA STRUCTURE, DS 授课教师：郭授课教师：郭 艳艳授课班级授课班级: 191091-4中国地质大学计算机学院中国地质大学计算机学院2019年春年春上堂课要点回顾上堂课要点回顾n图的基本概念与抽象数据类型定义图的基本概念与抽象数据类型定义n连通图、连通分量、生成树连通图、连通分量、生成树n度、入度、出度度、入度、出度n图的设计与实现图的设计与实现ACBG1n邻接矩阵邻接矩阵000101010,11ACBAVn邻接表邻接表0 A1 B2 C 2 1 0两种图存储结构的比较两种图存储结构的比较设设G是顶点数为是顶点数为n

2、，边数为边数为e的有向图，的有向图，d是顶点是顶点v或或v1的出度的出度基本操作基本操作邻接矩阵法邻接矩阵法邻接表法邻接表法GraphInitiate(G)O(1)O(1)IsVertex(G,vertex) O(n)O(n)InsertVertex(G,vertex)O(1)O(1)IsEdge(G,v1,v2)O(1)O(d)InsertEdge(G,v1,v2,weight)O(1)O(1)*Degree(G,v) O(n)O(d)DeleteEdge(G,v1,v2)O(1)O(d)DeleteVertex(G,v)O(n2)O(e)GetFirstVex(G,v)O(n)O(1)Ge

3、tNextVex(G,v1,v2)O(n)O(d)第第 十四次十四次 课课阅读：阅读： 朱战立，第朱战立，第224-228页、第页、第242-245页页习题：习题：作业作业13数据结构课程内容数据结构课程内容图结构的应用图结构的应用9.4 9.4 图的遍历图的遍历n什么叫图的遍历？什么叫图的遍历？n 已知图已知图G(V,E) ，从图中的任一顶，从图中的任一顶点出发，按一定规则顺着某些边去访问点出发，按一定规则顺着某些边去访问图中其余顶点，使每一个顶点被访问一图中其余顶点，使每一个顶点被访问一次且仅被访问一次。次且仅被访问一次。n 遍历的方法：遍历的方法：n 深度优先搜索深度优先搜索n 广度优先

4、搜索广度优先搜索9.4 图的遍历续）图的遍历续）n图的遍历从一个顶点图的遍历从一个顶点v出发，试探性地访出发，试探性地访问其余顶点，必须考虑到下列情况：问其余顶点，必须考虑到下列情况：n从一顶点出发，可能不能到达所有其它从一顶点出发，可能不能到达所有其它的顶点只能到达的顶点只能到达v所在连通分量的所有所在连通分量的所有顶点），如非连通图；顶点），如非连通图；n有可能会陷入死循环，如存在回路的图有可能会陷入死循环，如存在回路的图。n解决办法解决办法n检查图的所有顶点是否被访问过，如果检查图的所有顶点是否被访问过，如果未被访问，则从该未被访问的顶点开始未被访问，则从该未被访问的顶点开始继续遍历继续

5、遍历n为每个顶点设置一个访问标志位为每个顶点设置一个访问标志位visit bit）。算法开始时，所有顶点的访问标）。算法开始时，所有顶点的访问标志位置零；在遍历的过程中，当某个顶志位置零；在遍历的过程中，当某个顶点被访问时，其标志位就被标记为已访点被访问时，其标志位就被标记为已访问。问。void GraphTraverse(AdjMGraph*G,void Visit(DataType item)/*遍历图，图采用邻接矩阵存储，访问顶点函数遍历图，图采用邻接矩阵存储，访问顶点函数Visit*/ int i;int *visited=(int *)malloc(sizeof(int)*G-Ver

6、tices.size); /*访问标志动态数组访问标志动态数组*/ for(i=0;vVertices.size;i+) visitedi=0; /*对所有顶点的标志位进行初始化对所有顶点的标志位进行初始化*/*检查图的所有顶点是否被访问过，如果未被访问，检查图的所有顶点是否被访问过，如果未被访问，则从该未被访问的顶点开始继续遍历，则从该未被访问的顶点开始继续遍历，do_Search函数函数可以调用用深度优先或者广度优先搜索函数可以调用用深度优先或者广度优先搜索函数*/ for(i=0;iVertices.size;i+) if(!visitedi) do_Search(G,i,visited

7、,Visit); 非连通图的深度优先搜索非连通图的深度优先搜索9.4 图的遍历续）图的遍历续）n图的生成树图的生成树n图图G的所有顶点加上遍历过程中经过的的所有顶点加上遍历过程中经过的边所构成的子图称作图边所构成的子图称作图G的生成树的生成树Gn特征特征n生成树生成树G是是G的极小连通子图的极小连通子图n生成树生成树G含有图含有图G中全部顶点，但只有中全部顶点，但只有n-1条边条边n生成树生成树G没有回路没有回路9.4 图的遍历续）图的遍历续）n图的生成森林图的生成森林n若一个图若一个图G是非连通图或非强连通图，是非连通图或非强连通图，通过遍历可以得到图通过遍历可以得到图G的生成森林的生成森林

8、G。n特征特征n若若G有有 n 个顶点，个顶点，m 个连通分量或强连个连通分量或强连通分量，则可以遍历得到通分量，则可以遍历得到m棵生成树，棵生成树，合起来为生成森林合起来为生成森林G，森林，森林G中包含中包含n-m条树边。条树边。n深度优先搜索深度优先搜索 (depth-first search, DFS)步骤步骤n 首先访问出发顶点首先访问出发顶点v，再访问一个与，再访问一个与v相相邻接的邻接的 且未被访问过的顶点且未被访问过的顶点w1；n 再从再从w1出发，递归地按照深度优先的方出发，递归地按照深度优先的方式遍历；式遍历；设访问顶点序列设访问顶点序列w1, w2, w3,n 当遇到一个所

9、有邻接点均被访问过的顶当遇到一个所有邻接点均被访问过的顶点点wt时时n 则沿刚才访问的次序，反向回到已访则沿刚才访问的次序，反向回到已访问顶点序列问顶点序列n中最后一个尚有邻接点未被访问过的中最后一个尚有邻接点未被访问过的顶点顶点ws；n 再从再从ws出发，递归地按照深度优先的方出发，递归地按照深度优先的方式遍历；式遍历； n 当所有被访问过的顶点都没有未被访问当所有被访问过的顶点都没有未被访问的邻接顶的邻接顶n点时，出发顶点点时，出发顶点v所在连通分量的遍所在连通分量的遍历结束。历结束。n 深度优先搜索树深度优先搜索树depth-first search tree）n例：例：81234567

10、G5深度优先搜索序列为：深度优先搜索序列为：v1v2v4v8v5v6v3v7或或v1v2v5v8v4v7v3v6 81234567G5的深度优先生成树G5 v1v21v42v831314v54512v6116v3107v79815void DepthFirstSearch(AdjMGraph *G, int v, int visited , void Visit(DataType item)/*图采用邻接矩阵为存储结构，从第图采用邻接矩阵为存储结构，从第v个顶点出发递归地深度优个顶点出发递归地深度优先遍历图。附设访问标志数组先遍历图。附设访问标志数组visitedn: visitedi=0(1

11、)，表，表示图中的第示图中的第i个顶点未个顶点未(已已)被访问过被访问过*/ int w; Visit(G-Vertices.listv); /*访问第访问第v个顶点个顶点*/visitedv=1; /*标记第标记第v个顶点已访问个顶点已访问*/ /*访问第访问第v个顶点邻接的未被访问过的顶点个顶点邻接的未被访问过的顶点w，并从，并从w出发递归出发递归地按照深度优先的方式进行遍历地按照深度优先的方式进行遍历*/ w=GetFirstVex(G,v); /*得到第得到第v个顶点的第一个邻接顶点个顶点的第一个邻接顶点w*/ while(w!= -1) if(!visitedw) DepthFSea

12、rch(G,w,visited,Visit);w=GetNextVex(G,v,w); /*得到第得到第v个顶点的下一个顶点的下一个邻接顶点个邻接顶点w*/ 算法算法 深度优先搜索算法分析深度优先搜索算法分析设图设图G有有n个顶点、个顶点、e条边。条边。DFS对每一条边处理一次，每个顶点访问一次对每一条边处理一次，每个顶点访问一次 以邻接矩阵作存储结构：处理所有的边需以邻接矩阵作存储结构：处理所有的边需O(n2)的时间的时间 ，故总代价为故总代价为O(n2)。 以邻接表作存储结构：由于对邻接表中的每个边结点仅检以邻接表作存储结构：由于对邻接表中的每个边结点仅检测一次，而边结点共有测一次，而边结

13、点共有2e个，所以处理所有的边的时间可记个，所以处理所有的边的时间可记为为O(e)，故总代价为，故总代价为O(n+e)。n广度优先搜索广度优先搜索(breadth-first search, BFS)n 步骤步骤n 访问起始顶点访问起始顶点v后，依次访问与后，依次访问与v相邻接的所相邻接的所有有 顶点顶点w1, w2, , wt；n 再按再按w1, w2, , wt的顺序，访问其中每一个的顺序，访问其中每一个顶点顶点 的所有未被访问过的邻接顶点；对的所有未被访问过的邻接顶点；对w1为：为：w11, w12, , w1m1；对；对wt为：为：wt1, wt2, , wtmt等；等；n 再按再按w

14、11, w12, , w1m1, w21, , w2m2, , wt1, , wtmt的的 顺序，去访问它们各自的未被访问过的邻接顶顺序，去访问它们各自的未被访问过的邻接顶 点。依次类推，直到点。依次类推，直到v所在连通分量中所有被所在连通分量中所有被访问过的访问过的顶点的邻接顶点都被访问过为止。顶点的邻接顶点都被访问过为止。n 广度优先搜索树广度优先搜索树depth-first search tree）例：例：81234567G5广度优先搜索序列为： v1v2v3v4v5v6v7v8 或 v1v3v2v6v7v5v4v8 81234567GG5的广度优先生成树 算法算法 图采用邻接矩阵为存储

15、结构。图采用邻接矩阵为存储结构。 void BreadthFirstSearch(AdjMGraph *G, int v, int visited , void Visit(DataType item) SeqCQueue queue; DataType w,u; QueueInitiate(&queue)；/*初始化队列初始化队列queue*/Visit(G-Vertices.listv); /*访问顶点访问顶点v*/visitedv=1; QueueAppend(&queue, v); /*将将v入队入队*/ while(QueueNotEmpty(queue)/*当队列不

16、为空时循环当队列不为空时循环*/ QueueDelete(&queue,&u); /*取出队头元素取出队头元素u*/ w=GetFirstVex(G,u); /*取取u的第一个邻接结点的第一个邻接结点w*/ while(w!= -1) if(!visitedw) Visit(G-Vertices.listw); /*访问顶点访问顶点w*/ visited(w)=1; QueueAppend(&queue, w); /*将将w入队入队*/ w=GetNextVex(G, u ,w);/*取取u的下一邻接点的下一邻接点*/ 广度优先搜索算法分析分析上述过程，每个顶点至多进一

17、次队列。分析上述过程，每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻遍历图的过程实质上是通过边或弧找邻接点的过程。因此广度优先搜索遍历图接点的过程。因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，的时间复杂度和深度优先搜索遍历相同，两者不同之处仅在于对顶点访问的顺序两者不同之处仅在于对顶点访问的顺序不同。不同。 9.7 拓扑排序拓扑排序topological sort）n先决条件问题先决条件问题n拓扑排序拓扑排序n将一个有向无将一个有向无环图中所有顶环图中所有顶点在不违反先点在不违反先决条件关系的决条件关系的前提下排成线前提下排成线性序列的过程性序列的过程称为拓扑排序称为

18、拓扑排序学生选修课程问题：学生选修课程问题：学生学生应按怎样的顺序应按怎样的顺序学习学习下列下列课程，才能课程，才能无矛盾、顺利地完成无矛盾、顺利地完成学业学业？课程代号课程名称 先修课C1程序设计基础无C2离散数学C1C3数据结构C1,C2C4汇编语言C1C5语言的设计和分析C3,C4C6计算机原理C11C7编译原理C3.C5C8操作系统C3,C6C9高等数学无 C10线性代数C9C11普通物理C9C12数值分析C1,C9,C10C1C2C3C4C5C6C7C8C9C10C11C12数学模型：有向无环图数学模型：有向无环图顶点顶点活动课程）活动课程）有向弧有向弧活动活动i是活动是活动j的优先

19、条件的优先条件序列序列1：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8序列序列2：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8Activity OnVertex network9.7 拓扑排序续）n拓扑序列拓扑序列(topological order)n对于有向无环图对于有向无环图G=（V，E），所有顶点），所有顶点组成的线性序列如果满足组成的线性序列如果满足n若在有向无环图若在有向无环图G中从顶点中从顶点Vi到到Vj有一有一条路径，则在序列中顶点条路径，则在序列中顶点Vi必在顶点必在顶点Vj之前。之前。n则该线性序列可称作一个拓

20、扑序列则该线性序列可称作一个拓扑序列n拓扑序列不唯一拓扑序列不唯一9.7 拓扑排序续）n任何有向无环图任何有向无环图G的所有顶点都可以排的所有顶点都可以排在一个拓扑序列里。在一个拓扑序列里。n拓扑排序的方法是：拓扑排序的方法是：n1、从图、从图G中选择一个入度为中选择一个入度为0的顶点并的顶点并输出。输出。n2、从图、从图G中删掉此顶点及其所有的出边中删掉此顶点及其所有的出边。n3、回到第、回到第1步继续执行，直至步继续执行，直至G所有顶所有顶点都被输出或点都被输出或G中不存在入度为中不存在入度为0的顶点的顶点。C1C2C3C4C5C6C7C8C9C10C11C12C2C3C4C5C6C7C8

21、C9C10C11C12（1拓扑序列：C1C3C4C5C6C7C8C9C10C11C12（2拓扑序列：C1-C2C4C5C6C7C8C9C10C11C12（3拓扑序列：C1-C2-C3C5C6C7C8C9C10C11C12（4拓扑序列：C1-C2-C3-C4C6C8C10C11C12（7拓扑序列：C1-C2-C3-C4 -C5-C7-C9C6C8C11C12（8拓扑序列：C1-C2-C3-C4 -C5-C7-C9-C10C6C7C8C9C10C11C12（5拓扑序列：C1-C2-C3-C4 -C5C6C8C9C10C11C12（6拓扑序列：C1-C2-C3-C4 -C5-C7C6C8C12（9拓

22、扑序列：C1-C2-C3-C4 -C5-C7-C9-C10-C11C8C12（10拓扑序列：C1-C2-C3-C4 -C5-C7-C9-C10-C11-C6C8（11拓扑序列：C1-C2-C3-C4 -C5-C7-C9-C10-C11-C6 -C12（12拓扑序列：C1-C2-C3-C4 -C5-C7-C9-C10-C11-C6 -C12-C8n拓扑排序算法首先需要计算各顶点的入度，然拓扑排序算法首先需要计算各顶点的入度，然后在拓扑排序过程中，当某个顶点的入度为零后在拓扑排序过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有直时，就将此顶点输出，同时将该顶点的所有直接后继顶点的

23、入度减接后继顶点的入度减1。为了避免重复检测入。为了避免重复检测入度为零的顶点，设立一个栈或队列），以保度为零的顶点，设立一个栈或队列），以保存当前所有存当前所有“入度为零的顶点入度为零的顶点n若有向若有向G中所有顶点都被输出，则表明中所有顶点都被输出，则表明G中没中没有有向环，拓扑排序成功。若仅输出了部分顶有有向环，拓扑排序成功。若仅输出了部分顶点，点，G中已不存在入度为中已不存在入度为0的顶点，则表明的顶点，则表明G中中存在有向环，拓扑排序失败。存在有向环，拓扑排序失败。n拓扑排序算法实现：设图拓扑排序算法实现：设图G G的顶点数为的顶点数为n n，采用邻接矩，采用邻接矩阵作为存储结构阵作

24、为存储结构n1 1、对各顶点求入度、对各顶点求入度n2 2、初始化栈、初始化栈S S，拓扑序列长度计数器，拓扑序列长度计数器sizesize初始化为初始化为0 0n3 3、把所有入度为、把所有入度为0 0的顶点入栈的顶点入栈S Sn4 4、当栈、当栈S S非空时循环非空时循环n4.1 4.1 输出栈顶元素输出栈顶元素v v并出栈；并出栈；size+size+；n4.2 4.2 获得所有与获得所有与v v邻接的未被访问的顶点邻接的未被访问的顶点w wn4.3 4.3 把把w w的入度减的入度减1 1；n4.4 4.4 若若w w的入度为的入度为0 0则入栈则入栈S Sn直至栈空为止直至栈空为止n5 5、如果、如果sizensizen，则有向图有环，不存在拓扑序列，则有向图有环，不存在拓扑序列，拓扑排序失败；否则