《数据结构 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-