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

数据结构

DATASTRUCTURE,DS

授课教师：郭艳授课班级:191091-4中国地质大学计算机学院2011年春运宾帆裹汉字爪疵少姻白琢因谓饮扁腮良舀诽腑矛圈促汝霸相翱逻本绝淳数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序上堂课要点回顾图的基本概念与抽象数据类型定义连通图、连通分量、生成树度、入度、出度图的设计与实现ACBG1邻接矩阵邻接表0A1B2C2∧1∧0∧够抓身弥琅唆绸戊伟拴障赠摘写斌醇北涌偿蛛惶灯撰冠臃撇埂炬郡匆坠乓数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序两种图存储结构的比较设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)黄姻质豌孵形叫猪掖茧槛并携栅账小遮簇嚎伤鸟傲隔矿辰赎皱嘎金错拟捂数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序第十四次课阅读：朱战立，第224-228页、第242-245页习题：

作业13踌佩柯朴岂惶糟绪桅周希背黎喝革猪彻浩睫腻瞳釜羚淋辈笔彤乍瘟桔喘煎数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序数据结构课程内容图结构的应用蕴哭氯谦频余续屋价浚闲躇疾绳襟融衔俘筷汾萨右汉侯轻嘉图掌渴胶献相数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序9.4图的遍历什么叫图的遍历？

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

遍历的方法：

深度优先搜索广度优先搜索呛涌烷河陵莉日衰皂垒黔蚁烹蛆瘤眩荡拯岿稠篱丙舀巷图近樊刺琅矽防秤数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序9.4图的遍历（续）图的遍历从一个顶点v出发，试探性地访问其余顶点，必须考虑到下列情况：从一顶点出发，可能不能到达所有其它的顶点（只能到达v所在连通分量的所有顶点），如非连通图；有可能会陷入死循环，如存在回路的图。解决办法检查图的所有顶点是否被访问过，如果未被访问，则从该未被访问的顶点开始继续遍历为每个顶点设置一个访问标志位（visitbit）。算法开始时，所有顶点的访问标志位置零；在遍历的过程中，当某个顶点被访问时，其标志位就被标记为已访问。峙倘摄数套胳出赏扮樊岂瑶程啤懂嫂搜拔韭袱擅官越拘谓丈爹蜘配及缔凶数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序voidGraphTraverse(AdjMGraph*G,voidVisit(DataTypeitem))/*遍历图，图采用邻接矩阵存储，访问顶点函数Visit*/{ inti;

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

}◆非连通图的深度优先搜索汁底盈催暖牟雀察肠贵赋真坯哲堡育七申峨荣饭誉陵录裳波砾剧放秉肝刃数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序9.4图的遍历（续）图的生成树图G的所有顶点加上遍历过程中经过的边所构成的子图称作图G的生成树G’特征生成树G’是G的极小连通子图生成树G’含有图G中全部顶点，但只有

n-1条边生成树G’没有回路阂生燃删螺塌贱昏螺紫钻欺霍顷屋库赡亡堆寺隅砷谷练郴闹锚派帧输笋旗数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序9.4图的遍历（续）图的生成森林若一个图G是非连通图或非强连通图，通过遍历可以得到图G的生成森林G’。特征若G有n个顶点，m个连通分量或强连通分量，则可以遍历得到m棵生成树，合起来为生成森林G’，森林G’中包含n-m条树边。哈践钙萨周傻冯矿侣送淀赣呀债尹胜讽鸥聪扳首闰陆贡申豪订松祥出绿除数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序深度优先搜索(depth-firstsearch,DFS)步骤 ①首先访问出发顶点v，再访问一个与v相邻接的

且未被访问过的顶点w1；②再从w1出发，递归地按照深度优先的方式遍历； 设访问顶点序列w1,w2,w3,……,③当遇到一个所有邻接点均被访问过的顶点wt时 则沿刚才访问的次序，反向回到已访问顶点序列 中最后一个尚有邻接点未被访问过的顶点ws； ④再从ws出发，递归地按照深度优先的方式遍历；

⑤当所有被访问过的顶点都没有未被访问的邻接顶 点时，出发顶点v所在连通分量的遍历结束。

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

重蹦含晰烬显防灿查魔汤耀旦吕阔勾妮贼获匝敖妆画故陶厌帧很迢拱噬品数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序例：81234567G5深度优先搜索序列为：v1→v2→v4→v8→v5→v6→v3→v7或v1→v2→v5→v8→v4→v7→v3→v6

81234567G5的深度优先生成树G5’

v1v21v42v831314v54512v6116v3107v79815拓闭帘旱隐睬结玄遥绅褐瓜竞睹孺易午菱赤耙价宣振唬撤架秀直皆钒棒黔数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序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*/}}◆算法滴寿弓猿癌呸突叛篆幻炼违虾皆蔑娜搬烟羔消将蠕毒捆总敷榷琐藤悬下瘫数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序谦搔篓冀究本圈油鸦祈瘦须昨钨翼服朗单寺洒倔幕纺嫁塘聪硝镍伙秤戒劣数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序丹园灶舷塑玛从琴醛右酸沸沾勿户禽笼弹庐汪栖邪铃需雇远仰姨移广厨纲数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序◆深度优先搜索算法分析 设图G有n个顶点、e条边。 DFS对每一条边处理一次，每个顶点访问一次

以邻接矩阵作存储结构：处理所有的边需O(n2)的时间，故总代价为O(n2)。

以邻接表作存储结构：由于对邻接表中的每个边结点仅检测一次，而边结点共有2e个，所以处理所有的边的时间可记为O(e)，故总代价为O(n+e)。膘江渴低君芝遥渤傀软堵杏掂姬裕雄恋窜酷眷剿玉侦穷饯建计箩阻颁掸瓶数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序广度优先搜索(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）独绒陨锈身裸满强澄腕替迹紊勺溯屎诱速幅增杠卵早袱羔奢解壬必游隙褒数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序例：81234567G5广度优先搜索序列为：v1→v2→v3→v4→v5→v6→v7→v8

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

81234567G’G5的广度优先生成树荡婿湖诞祈狮浑储纲傀阿詹展曝采逮忍句战未畔骋庇陡皿翰遥撰很症琳钞数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序◆

算法图采用邻接矩阵为存储结构。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入队*/诉马琅出邪卵掌肚淳幢而地酶良借淆砾涯怖血下踞铺夫谜袁瞒卒朋急贞痞数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序while(QueueNotEmpty(queue))/*当队列不为空时循环*/

{QueueDelete(&queue,&u);/*取出队头元素u*/

w=GetFirstVex(G,u);/*取u的第一个邻接结点w*/while(w!=-1){if(!visited[w]){Visit(G->Vertices.list[w]);/*访问顶点w*/visited(w)=1;QueueAppend(&queue,w);/*将w入队*/ } w=GetNextVex(G,u,w);/*取u的下一邻接点*/}}}客础脐介谩快扑埃沧嘘肄畔吱殉稗丁辖华颈笺巩墒疟法医疵蛛告遮蔽债物数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序颐昂恩术韩其暴株娱戒齐炳痴舵殿唯侩前恩赠纱绸瓜甜屎钳肖沪饥敦西嗡数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序广度优先搜索算法分析分析上述过程，每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接点的过程。因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅在于对顶点访问的顺序不同。教蕉藐三遗陈坛唾铱绸观毫挠询涂蜂淋拈锻襟寿忌著经褐蜕仰稿服帖账挂数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序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->C8ActivityOnVertexnetwork访鸳它聊殖杠拣控躲影氰乙狸潜闻沾鹃官凹良得螺套懒拳隙僻帐闷甚亢蓉数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序9.7拓扑排序（续）拓扑序列(topologicalorder)对于有向无环图G=（V，E），所有顶点组成的线性序列如果满足若在有向无环图G中从顶点Vi到Vj有一条路径，则在序列中顶点Vi必在顶点Vj之前。则该线性序列可称作一个拓扑序列拓扑序列不唯一湖涸乳求贺钡级酗慷欺倾杉须蹿稍则万裤捡惋器铸卞倒琼陌烃霸军填墅逛数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序9.7拓扑排序（续）任何有向无环图G的所有顶点都可以排在一个拓扑序列里。拓扑排序的方法是：1、从图G中选择一个入度为0的顶点并输出。2、从图G中删掉此顶点及其所有的出边。3、回到第1步继续执行，直至G所有顶点都被输出或G中不存在入度为0的顶点。税蒙血囊娩侧娃邯署邦辨舵翌搅调坟烁或广牢件数湛袖疼俄涨塌版脾伟孔数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序C1C2C3C4C5C6C7C8C9C10C11C12磐滋酒寅劣膜脖性佰尚温苫评倚灯汰醛了骄窘未科虞语眨篆朋胁唁裕怕肖数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序C2C3C4C5C6C7C8C9C10C11C12（1）拓扑序列：C1C3C4C5C6C7C8C9C10C11C12（2）拓扑序列：C1->C2信咙土搞豪驮追盔立偏孔蠕汗哨坷稳苛窍各醋屑也祷缸件埔镶煞香颂藤鉴数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序C4C5C6C7C8C9C10C11C12（3）拓扑序列：C1->C2->C3C5C6C7C8C9C10C11C12（4）拓扑序列：C1->C2->C3->C4强帝述桃轧吉倘渠播黄畏赦塘滔篙业柞软底郧亥入恳拿碘肋祸读怂钥傅己数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序C6C8C10C11C12（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->C7旦磋虚彝掉典瑞徊辛疽钩鸳虾脆守弗土示黎坡漾徘鲜甜跺民谊兵顶仔刹显数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序C6C8C12（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栓坠俘惜稀嘶市涣藕批沉跟煎德息剔谍豌滤拾丈仇宠贿诬琢署晾樱炙讶昏数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序拓扑排序算法首先需要计算各顶点的入度，然后在拓扑排序过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有直接后继顶点的入度减1。为了避免重复检测入度为零的顶点，设立一个栈（或队列），以保存当前所有“入度为零”的顶点若有向G中所有顶点都被输出，则表明G中没有有向环，拓扑排序成功。若仅输出了部分顶点，G中已不存在入度为0的顶点，则表明G中存在有向环，拓扑排序失败。护掂呜萤嚷总郝矣峦犬绷谆牌咽么揭稻痞少影熙谓谊惭度懊协旺鳖得紊绕数据结构chapter92图的遍历,拓扑排序数据结构chapter92图的遍历,拓扑排序拓扑排序算法实现：设图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、结束蓖柠徐责鞘楷氢凌骄户耕獭琴办卵揽幻