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

1、数数 据据 结结 构构 data structure, ds 授课教师：郭授课教师：郭 艳艳授课班级授课班级: 191091-4中国地质大学计算机学院中国地质大学计算机学院2011年春年春上堂课要点回顾上堂课要点回顾n图的基本概念与抽象数据类型定义图的基本概念与抽象数据类型定义n连通图、连通分量、生成树连通图、连通分量、生成树n度、入度、出度度、入度、出度n图的设计与实现图的设计与实现acbg1n邻接矩阵邻接矩阵000101010,11acbavn邻接表邻接表0 a1 b2 c 2 1 0两种图存储结构的比较两种图存储结构的比较设设g是顶点数为是顶点数为n，边边数为数为e的的有向图，有向图，d

2、是顶点是顶点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)getnextvex(g,v1,v2)o(

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

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

5、visit bit）。）。算法开始时，所有顶点的访问标志位置零；在遍算法开始时，所有顶点的访问标志位置零；在遍历的过程中，当某个顶点被访问时，其标志位就历的过程中，当某个顶点被访问时，其标志位就被标记为已访问。被标记为已访问。void graphtraverse(adjmgraph*g,void visit(datatype item)/*遍历图，图采用邻接矩阵存储，访问顶点函数遍历图，图采用邻接矩阵存储，访问顶点函数visit*/ int i;int *visited=(int *)malloc(sizeof(int)*g-vertices.size); /*访问标志动态数组访问标志动态数组

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

7、9.4 图的遍历（续）图的遍历（续）n图的生成树图的生成树n图图g的所有顶点加上遍历过程中经过的边所的所有顶点加上遍历过程中经过的边所构成的子图称作构成的子图称作图图g的生成树的生成树gn特征特征n生成树生成树g是是g的的极小连通极小连通子图子图n生成树生成树g含有图含有图g中全部顶点，但只有中全部顶点，但只有n-1条边条边n生成树生成树g没有回路没有回路9.4 图的遍历（续）图的遍历（续）n图的生成森林图的生成森林n若一个图若一个图g是非连通图或非强连通图，通过是非连通图或非强连通图，通过遍历可以得到图遍历可以得到图g的的生成森林生成森林g。n特征特征n若若g有有 n 个顶点，个顶点，m 个

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

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

10、或或v1v2v5v8v4v7v3v6 81234567g5的的深度优先深度优先生成树生成树g5 v1v21v42v831314v54512v6116v3107v79815void depthfirstsearch(adjmgraph *g, int v, int visited , void visit(datatype item)/*图采用图采用邻接矩阵邻接矩阵为存储结构，从第为存储结构，从第v个顶点出发递归地个顶点出发递归地深度优深度优先遍历图先遍历图。附设。附设访问标志数组访问标志数组visitedn: visitedi=0(1)，表，表示图中的第示图中的第i个顶点未个顶点未(已已)被访

11、问过被访问过*/ int w; visit(g-vertices.listv); /*访问第访问第v个顶点个顶点*/visitedv=1; /*标记第标记第v个顶点已访问个顶点已访问*/ /*访问第访问第v个顶点邻接的未被访问过的顶点个顶点邻接的未被访问过的顶点w，并从，并从w出发递归出发递归地按照深度优先的方式进行遍历地按照深度优先的方式进行遍历*/ w=getfirstvex(g,v); /*得到第得到第v个顶点的第一个邻接顶点个顶点的第一个邻接顶点w*/ while(w!= -1) if(!visitedw) depthfsearch(g,w,visited,visit);w=getne

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

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

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

15、stsearch(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)/*当队列不为空时循环当队列不为空时循环*/ queuedelete(&am

16、p;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的的优先优先条件条件序列序列1：c1-c2-c3-c4-c5-c

19、7-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、列不唯一9.7 拓扑排序（续）n任何有向无环图任何有向无环图g的所有顶点都可以排的所有顶点都可以排在一个拓扑序列里。在一个拓扑序列里。n拓扑排序的方法是：拓扑排序的方法是：n1、从图、从图g中选择一个入度为中选择一个入度为0的顶点并输的顶点并输出。出。n2、从图、从图g中删掉此顶点及其所有的出边。中删掉此顶点及其所有的出边。n3、回到第、回到第1步继续执行，直至步继续执行，直至g所有顶点都被输出或g中不存在入度为0的顶点。c1c2c3c4c5c6c7c8c9c10c11c12c2c3c4c5c6c7c8c9c10c11c12（1）拓扑序列：c1c3c4c5c6c7c8c9c10c11c12（2

21、）拓扑序列：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）拓扑序列：c1-c2-c3-c4 -c5-c7-c9-c10-c11c8c1

22、2（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拓扑排序算法首先需要计算拓扑排序算法首先需要计算各顶点的入度，然各顶点的入度，然后后在拓扑排序过程中，当某个顶点的入度为零在拓扑排序过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有直时，就将此顶点输出，同时将该顶点的所有直接后继顶点的入度减接后继顶点的入度减1。为了避免重复检测入。为了避免重复检测入度

23、为零的顶点，度为零的顶点，设立一个栈（或队列），以保设立一个栈（或队列），以保存当前所有存当前所有“入度为零入度为零”的顶点的顶点n若有向若有向g中所有顶点都被输出中所有顶点都被输出，则表明，则表明g中没中没有有向环，拓扑排序成功。若仅输出了部分顶有有向环，拓扑排序成功。若仅输出了部分顶点，点，g中已不存在入度为中已不存在入度为0的顶点，则表明的顶点，则表明g中中存在有向环，拓扑排序失败。存在有向环，拓扑排序失败。n拓扑排序算法实现：设图拓扑排序算法实现：设图g g的顶点数为的顶点数为n n，采用邻接矩，采用邻接矩阵作为存储结构阵作为存储结构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