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

数据结构

DATASTRUCTURE,DS

授课教师：郭艳授课班级:191091-42011上堂课要点回顾图的基本概念与抽象数据类型定义连通图、连通分量、生成树度、入度、出度图的设计与实现ACBG1邻接矩阵邻接表0A1B2C2∧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)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(n)O(d)数据结构课程内容图结构的应用9.4图的遍历什么叫图的遍历？

已知图G(V,E)

，从图中的任一顶点出发，按一定规则顺着某些边去访问图中其余顶点，使每一个顶点被访问一次且仅被访问一次。

遍历的方法：

深度优先搜索广度优先搜索9.4图的遍历（续）图的遍历从一个顶点v出发，试探性地访问其余顶点，必须考虑到下列情况：从一顶点出发，可能不能到达所有其它的顶点（只能到达v所在连通分量的所有顶点），如非连通图；有可能会陷入死循环，如存在回路的图。解决办法检查图的所有顶点是否被访问过，如果未被访问，则从该未被访问的顶点开始继续遍历为每个顶点设置一个访问标志位（visitbit）。算法开始时，所有顶点的访问标志位置零；在遍历的过程中，当某个顶点被访问时，其标志位就被标记为已访问。9.4图的遍历（续）图的生成树图G的所有顶点加上遍历过程中经过的边所构成的子图称作图G的生成树G’特征生成树G’是G的极小连通子图生成树G’含有图G中全部顶点，但只有

n-1条边生成树G’没有回路9.4图的遍历（续）图的生成森林若一个图G是非连通图或非强连通图，通过遍历可以得到图G的生成森林G’。特征若G有n个顶点，m个连通分量或强连通分量，则可以遍历得到m棵生成树，合起来为生成森林G’，森林G’中包含n-m条树边。深度优先搜索

(depth-firstsearch,DFS)步骤

①首先访问出发顶点v，再访问一个与v相邻接的

且未被访问过的顶点w1；②再从w1出发，递归地按照深度优先的方式遍历；

设访问顶点序列w1,w2,w3,……,③当遇到一个所有邻接点均被访问过的顶点wt时

则沿刚才访问的次序，反向回到已访问顶点序列

中最后一个尚有邻接点未被访问过的顶点ws；

④再从ws出发，递归地按照深度优先的方式遍历；

⑤当所有被访问过的顶点都没有未被访问的邻接顶

点时，出发顶点v所在连通分量的遍历结束。

深度优先搜索树（depth-firstsearchtree）

voidDepthFirstSearch(AdjMGraph*G,intv,intvisited[],voidVisit(DataTypeitem))/*图采用邻接矩阵为存储结构，从第v个顶点出发递归地深度优先遍历图。附设访问标志数组visited[n]:

visited[i]=0(1)，表示图中的第i个顶点未(已)被访问过*/{intw;Visit(G->Vertices.list[v]);/*访问第v个顶点*/

visited[v]=1; /*标记第v个顶点已访问*/

/*访问第v个顶点邻接的未被访问过的顶点w，并从w出发递归地按照深度优先的方式进行遍历*/w=GetFirstVex(G,v);/*得到第v个顶点的第一个邻接顶点w*/while(w!=-1){ if(!visited[w])DepthFSearch(G,w,visited,Visit); w=GetNextVex(G,v,w);/*得到第v个顶点的下一

个邻接顶点w*/}}◆算法广度优先搜索(breadth-firstsearch,BFS)◆

步骤①访问起始顶点v后，依次访问与v相邻接的所有

顶点w1,w2,…,wt；②再按w1,w2,…,wt的顺序，访问其中每一个顶点

的所有未被访问过的邻接顶点；对w1为：w11,

w12,…,w1m1；…；对wt为：wt1,wt2,…,wtmt等；③再按w11,w12,…,w1m1,w21,…,w2m2,

…,wt1,…,wtmt的

顺序，去访问它们各自的未被访问过的邻接顶

点。依次类推，直到v所在连通分量中所有被访问过的

顶点的邻接顶点都被访问过为止。

◆

广度优先搜索树（depth-firstsearchtree）例：81234567G5广度优先搜索序列为：

v1→v2→v3→v4→v5→v6→v7→v8

或v1→v3→v2→v6→v7→v5→v4→v8

81234567G’G5的广度优先生成树◆

算法图采用邻接矩阵为存储结构。

voidBreadthFirstSearch(AdjMGraph*G,intv,intvisited[],voidVisit(DataTypeitem)){SeqCQueuequeue;DataTypew,u;QueueInitiate(&queue)；/*初始化队列queue*/ Visit(G->Vertices.list[v]);/*访问顶点v*/ visited[v]=1;QueueAppend(&queue,v);/*将v入队*/广度优先搜索算法分析分析上述过程，每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接点的过程。因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅在于对顶点访问的顺序不同。9.7拓扑排序（topologicalsort）先决条件问题拓扑排序将一个有向无环图中所有顶点在不违反先决条件关系的前提下排成线性序列的过程称为拓扑排序学生选修课程问题：学生应按怎样的顺序学习下列课程，才能无矛盾、顺利地完成学业？课程代号课程名称先修课C1程序设计基础无C2离散数学C1C3数据结构C1,C2C4汇编语言C1C5语言的设计和分析C3,C4C6计算机原理C11C7编译原理C3.C5C8操作系统C3,C6C9高等数学无

C10线性代数C9C11普通物理C9C12数值分析C1,C9,C10C1C2C3C4C5C6C7C8C9C10C11C12数学模型：有向无环图顶点——活动（课程）有向弧<i,j>——活动i是活动j的优先条件序列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->C8ActivityOnVertexnetwork9.7拓扑排序（续）任何有向无环图G的所有顶点都可以排在一个拓扑序列里。拓扑排序的方法是：1、从图G中选择一个入度为0的顶点并输出。2、从图G中删掉此顶点及其所有的出边。3、回到第1步继续执行，直至G所有顶点都被输出或G中不存在入度为0的顶点。C1C2C3C4C5C6C7C8C9C10C11C12C6C8C10C11C12（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->C9->C10->C11->C6->C12（12）拓扑序列：C1->C2->C3->C4->C5->C7->C9->C10->C11->C6->C12->C8拓扑排序算法首先需要计算各顶点的入度，然后在拓扑排序过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有直接后继顶点的入度减1。为了避免重复检测入度为零的顶点，设立一个栈（或队列），以保存当前所有“入度为零”的顶点若有向G中所有顶点都被输出，则表明G中没有有向环，拓扑排序成功。若仅输出了部分顶点，G中已不存在入度为0的顶点，则表明G中存在有向环，拓扑排序失败。拓扑排序算法实现：设图G的顶点数为n，采用邻接矩阵作为存储结构1、对各顶点求入度2、初始化栈S，拓扑序列长度计数器size初始化为03、把所有入度为0的顶点入栈S4、当栈S非空时循环4.1输出栈顶元素v并出栈；size++；4.2获得所有与v邻接的未被访问的顶点w4.3把w的入度减1；4.4若w的入度为0则入栈S

直至栈空为止5、如果size<>n，则有向图有环，不存在拓扑序列，拓扑排序失败；否则，拓扑排序成功6、结束9.7拓扑排序（续）拓扑排序算法的时间复杂度分析关键是，算法在开始时要找出所有入度为0的顶点（同时可知道其它顶点的入度）当采用邻接矩阵时，算法在开始时找所有入度为0的顶点需要O(n2)的时间，加上处理边、顶点的时间，总代价为O(n2+e+n)=O(n2)当采用邻接表时，因为在顶点表的每个顶点中可以有一个字段来存储入度，所以算法在开始时找所有入度为0的顶点只需要O(e)的时间，加上处理边、顶点的时间，总代价为O(n+2e)=O(n+e)作业13概念题：P249，9-3，9-13第二次上机实习——教学计划编制问题大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是