《数据结构 chapter 9(2)图的遍历,拓扑排序》由会员分享，可在线阅读，更多相关《数据结构 chapter 9(2)图的遍历,拓扑排序（36页珍藏版）》请在金锄头文库上搜索。
1、数 据 结 构 DATA STRUCTURE, DS 授课教师：郭 艳 授课班级: 191091-4中国地质大学计算机学院 2011年春上堂课要点回顾n图的基本概念与抽象数据类型定义n连通图、连通分量、生成树n度、入度、出度n图的设计与实现ACBG1n邻接矩阵n邻接表0 A1 B2 C2 1 0两种图存储结构的比较设设G是顶顶点数为为n，边边数为为e的有向图图， d是顶顶点v或v1的出度基本操作邻邻接矩阵阵法邻邻接表法 GraphInitiate(G)O(1)O(1) IsVertex(G,vertex) O(n)O(n) InsertVertex(G,vertex)O(1)O(1) IsEd
2、ge(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(n)O(d)第 十四次 课阅读：朱战立，第224-228页、第242- 245页习题： 作业13数据结构课程内容图结构的应用9.4 图的遍历n什么叫图的遍历？已知图G(V,E) ，从图中的任一顶点出发 ，按一定规则顺着某些边去访问图中其余顶 点
3、，使每一个顶点被访问一次且仅被访问一 次。遍历的方法：深度优先搜索广度优先搜索9.4 图的遍历（续）n图图的遍历历从一个顶顶点v出发发，试试探性地 访问访问 其余顶顶点，必须须考虑虑到下列情况：n从一顶顶点出发发，可能不能到达所有其它的顶顶点 （只能到达v所在连连通分量的所有顶顶点），如非 连连通图图；n有可能会陷入死循环环，如存在回路的图图。n解决办办法n检查图检查图 的所有顶顶点是否被访问过访问过 ，如果未被访访 问问，则则从该该未被访问访问 的顶顶点开始继续继续 遍历历n为为每个顶顶点设设置一个访问访问 标标志位（visit bit）。 算法开始时时，所有顶顶点的访问标访问标 志位置零；
4、在 遍历历的过过程中，当某个顶顶点被访问时访问时 ，其标标志 位就被标记为标记为 已访问访问 。void GraphTraverse(AdjMGraph*G,void Visit(DataType item) /*遍历图历图 ，图图采用邻邻接矩阵阵存储储，访问顶访问顶 点函数Visit*/ int i; int *visited=(int *)malloc(sizeof(int)*G-Vertices.size); /*访问标访问标 志动态动态 数组组*/for(i=0;vVertices.size;i+) visitedi=0; /*对对所有顶顶点的标标志位进进行初始化*/ /*检查图检查图
5、 的所有顶顶点是否被访问过访问过 ，如果未被访问访问 ， 则则从该该未被访问访问 的顶顶点开始继续继续 遍历历，do_Search函 数可以调调用用深度优优先或者广度优优先搜索函数*/for(i=0;iVertices.size;i+)if(!visitedi) do_Search(G,i,visited,Visit); 非连通图的深度优先搜索9.4 图的遍历（续）n图图的生成树树n图图G的所有顶顶点加上遍历过历过 程中经过经过 的边边 所构成的子图图称作图图G的生成树树Gn特征n生成树树G是G的极小连连通子图图n生成树树G含有图图G中全部顶顶点，但只有 n-1条边边n生成树树G没有回路9.4
6、 图的遍历（续）n图的生成森林n若一个图G是非连通图或非强连通图，通过 遍历可以得到图G的生成森林G。n特征n若G有 n 个顶点，m 个连通分量或强连通 分量，则可以遍历得到m棵生成树，合起 来为生成森林G，森林G中包含n-m条树 边。n深度优先搜索 (depth-first search, DFS)步骤 首先访问出发顶点v，再访问一个与v相邻接的且未被访问过的顶点w1； 再从w1出发，递归地按照深度优先的方式遍历；设访问顶点序列w1, w2, w3, 当遇到一个所有邻接点均被访问过的顶点wt时则沿刚才访问的次序，反向回到已访问顶点序列中最后一个尚有邻接点未被访问过的顶点ws； 再从ws出发，
7、递归地按照深度优先的方式遍历； 当所有被访问过的顶点都没有未被访问的邻接顶点时，出发顶点v所在连通分量的遍历结束。n 深度优先搜索树（depth-first search tree）例：81234567G5深度优先搜索序列为： v1v2v4v8v5v6v3v7或 v1v2v5v8v4v7v3v6 81234567G5的 深度优先 生成树 G5 v1v21v42v831314v54512 v6116v3107v79815void DepthFirstSearch(AdjMGraph *G, int v, int visited , void Visit(DataType item) /*图采用邻
8、接矩阵为存储结构，从第v个顶点出发递归地深度优 先遍历图。附设访问标志数组visitedn: visitedi=0(1)，表 示图中的第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) DepthFSearch(G,w,visited,Visit); w
9、=GetNextVex(G,v,w); /*得到第v个顶点的下一 个邻接顶点w*/ 算法 深度优先搜索算法分析 设图G有n个顶点、e条边。 DFS对每一条边处理一次，每个顶点访问一次以邻接矩阵作存储结构：处理所有的边需O(n2) 的时间 ，故总代价为O(n2)。以邻接表作存储结构：由于对邻接表中的每个边 结点仅检测一次，而边结点共有2e个，所以处理所 有的边的时间可记为O(e)，故总代价为O(n+e)。n广度优先搜索(breadth-first search, BFS) 步骤 访问起始顶点v后，依次访问与v相邻接的所有顶点w1, w2, , wt； 再按w1, w2, , wt的顺序，访问其中
10、每一个顶点的所有未被访问过的邻接顶点；对w1为：w11,w12, , w1m1；对wt为：wt1, wt2, , wtmt等； 再按w11, w12, , w1m1, w21, , w2m2, , wt1, , wtmt的顺序，去访问它们各自的未被访问过的邻接顶点。依次类推，直到v所在连通分量中所有被访问过的 顶点的邻接顶点都被访问过为止。 广度优先搜索树（depth-first search tree）例：81234567G5广度优先搜索序列为：v1v2v3v4v5v6v7v8 或 v1v3v2v6v7v5v4v8 81234567GG5的广度优先生成树 算法图采用邻接矩阵为存储结构。voi
11、d BreadthFirstSearch(AdjMGraph *G, int v, int visited , void Visit(DataType item) SeqCQueue queue;DataType w,u;QueueInitiate( /*访问顶点v*/ visitedv=1;QueueAppend( /*将v入队*/while(QueueNotEmpty(queue)/*当队列不为空时循环*/ QueueDelete( /*取出队头元素u*/ w=GetFirstVex(G,u); /*取u的第一个邻接结点w*/while(w!= -1) if(!visitedw) Visi
12、t(G-Vertices.listw); /*访问顶点w*/visited(w)=1; QueueAppend( /*将w入队*/w=GetNextVex(G, u ,w);/*取u的下一邻接点*/ 广度优先搜索算法分析分析上述过程，每个顶点至多进一次队列 。遍历图的过程实质上是通过边或弧找 邻接点的过程。因此广度优先搜索遍历 图的时间复杂度和深度优先搜索遍历相 同，两者不同之处仅在于对顶点访问的 顺序不同。 9.7 拓扑排序（topological sort）n先决条件问题n拓扑排序n将一个有向 无环图中所 有顶点在不 违反先决条 件关系的前 提下排成线 性序列的过 程称为拓扑 排序学生选修
13、课程问题： 学生应按怎样的顺序 学习下列课程，才能 无矛盾、顺利地完成 学业？ 课程 代号课程名称 先修课C1程序设计基础无 C2离散数学C1 C3数据结构C1,C2 C4汇编语言C1 C5语言的设计和分析C3,C4 C6计算机原理C11 C7编译原理C3.C5 C8操作系统C3,C6 C9高等数学无 C10线性代数C9 C11普通物理C9 C12数值分析C1,C9,C10C1C2C3C4C5C6C7C8C9C10C11C12数学模型：有向无环图 顶点活动（课程） 有向弧活动i 是活动j的优先条件序列1：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8 序列2：C9
14、-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8Activity On Vertex network9.7 拓扑排序（续）n拓扑序列(topological order)n对对于有向无环环图图G=（V，E），所有顶顶点组组 成的线线性序列如果满满足n若在有向无环图环图 G中从顶顶点Vi到Vj有一条路径， 则则在序列中顶顶点Vi必在顶顶点Vj之前。 则该线则该线 性序列可称作一个拓扑序列n拓扑序列不唯一9.7 拓扑排序（续）n任何有向无环图环图 G的所有顶顶点都可以排 在一个拓扑序列里。n拓扑排序的方法是：n1、从图图G中选择选择 一个入度为为0的顶顶点并输输 出。n2、
15、从图图G中删删掉此顶顶点及其所有的出边边。n3、回到第1步继续执继续执 行，直至G所有顶点 都被输出或G中不存在入度为0的顶点。C1C2C3C4C5C6C7C8C9C10C11C12C2C3C4C5C6C7C8C9C10C11C12（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）拓扑序列：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-
