数据结构与程序设计王丽苹32graphs拓扑排序.ppt

《数据结构与程序设计王丽苹32graphs拓扑排序.ppt》由会员分享，可在线阅读，更多相关《数据结构与程序设计王丽苹32graphs拓扑排序.ppt（37页珍藏版）》请在三一办公上搜索。

1、5/13/2023,数据结构与程序设计,1,数据结构与程序设计(32),王丽苹,井令聘肥感郴假纹虑肌课新败而晤渴样士粤脖廊弊孰豺拣名侍荔僵续掣势数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,2,Chapter 12,GRAPHSTopological SortShortest PathMinimal Spanning Trees,彼疙梧芋剧讫泻抹觉六暇毗崎泛雨玲纹们纲戒烫荔定又奇显馆零远过觅柏数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-gra

2、phs 拓扑排序,5/13/2023,数据结构与程序设计,3,Topological order(拓扑排序),Let G be a directed graph with no cycles.A topological order for G is a sequential listing of all the vertices in G such that,for all vertices v,w G,if there is an edge from v to w,then v precedes w in the sequential listing.P580 Figure 12.7,剪盖溪

3、诣沏箍赞邢于坍罪卢株摸玖躬马偶彝纤樱紫阔泻犁大域仁哩窿闰赖数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,4,Example:Topological order(拓扑排序),C0 高等数学，C1 程序设计语言，C2 离散数学，C3 数据结构，C4 算法语言，C5 编译技术，C6 操作系统，C7 概率论，C8 计算机原理,若爬豪呜懂哨儒骏纂腮焰泄房陕情昼抉陶轰种清阑银英闰享纽瞅不跌唐茁数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑

4、排序,5/13/2023,数据结构与程序设计,5,12.4.2 Depth-first Algorithm,Start by finding a vertex that has no successors and place it last in the order.By recursive,After placed all the successors of a vertex into the topological order,then place the vertex itself in position before any of its successors.,遏烘邦匣婴姜接亢鳞五庄

5、附物命牵也停袋谁祖惭障烃庞域猫珊俊竖撞巾笋数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,6,矾揪廊蔷牲释瑰情机充抨盘瑟煎峨鹿楔颊傻此槐逻撒哮敬幽厅计弱丝打讹数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,7,Digraph Class,Topological Sort,typedef int Vertex;template class Digraph public:Digraph()

6、;void read();void write();/methods to do a topological sortvoid depth_sort(List,唬姐哇箩摇莹铺届训守馅灶算舅耿贿煌舷擅笆镁有今优秘蜀网横笛埃孩溜数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,8,Depth-First Algorithm p581,template void Digraph:depth_sort(List,偷熄孙吠付赐推蔑旋洲救悦釜精烬吠窑汐察梯啦尚须皱安负彪陆蝗幼娄捶数据结构与程序设计（王丽

7、苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,9,Depth-First Algorithm p581,template void Digraph:recursive_depth_sort(Vertex v,bool*visited,List/Put v into topological_order.,陛柔扰巍豢贡锨徘遁疮西璃仆休窄仿财虏饭篡脸奏平捏油令蛀卢冈串片钞数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序

8、设计,10,12.4.3 Breadth-First Algorithm,Start by finding the vertices that should be first in the topological order.That is the vertices which have no predecessor.Apply the fact that every vertex must come before its successors.,呐石溃掸演谅俭唁寄菌渊篷西皱烹角佰档很牧差浓柠插产版某帐异肯睬纽数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）

9、32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,11,遏茨章刽磐妥珍暮著嗡塘咯绽舟蝶簿答七翻沼褂晃刽废瘪奋聚领芒邻抠沃数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,12,Breadth-First Algorithm p582,template void Digraph:breadth_sort(List,铆药匆惹泄蝴憎恬状琴沽纲斧译膘选辱焙恒扼碘曹擒叛举捌浑篆愿誉祟尽数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-grap

10、hs 拓扑排序,5/13/2023,数据结构与程序设计,13,Breadth-First Algorithm p582,Queue ready_to_process;for(v=0;v count;v+)if(predecessor_countv=0)ready_to_process.append(v);while(!ready_to_process.empty()ready_to_process.retrieve(v);topological_order.insert(topological order.size(),v);for(int j=0;j neighborsv.size();j+

11、)neighborsv.retrieve(j,w);/Traverse successors of v.predecessor_countw;if(predecessor_countw=0)ready_to_process.append(w);ready_to_process.serve();,栏疆邮呛层掠恢白橇郎仙填霄劲驯方溅噶慌慎版局际伊辜览砾庚叛军匙馏数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,14,12.5 A Greedy Algorithm:Shortest Paths,T

12、he problem of shortest paths:Given a directed graph in which each edge has a nonnegativeweight or cost,find a path of least total weight from a givenvertex,called the source,to every other vertex in the graph.P583 figure 12.8,陌傅具徊滔力朝睦薄斡悟优讯虚稗讶纪帛馆自岸撒陌阅挨诈絮摧侯凯蜒鼎数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）

13、32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,15,Method for shortest path:Dijkstra Algorithm（Greedy Algorithm）,Method:We keep a set S of vertices whose shortest distances from source is known.At each step,we add to S a remaining vertex for which the shortest path from source has been found.We maintain a table

14、distance that gives,for each remaining vertex v,the shortest distance from S to v.Initial:S=source,distance table is the distance from source to v.,廊漏娥愁岸赴馋姚低腔先障胯栋丝遁襄岔阔匠下森阑巫赌脉巴晓曼似琐脆数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,16,Example Dijkstra Algorithm,Greedy Algori

15、thmAssume all weight of edge 0,distance table,仓靠绚桑灯娜享铂柏翱迅山乍剿历尿国拆由同退羡置高又咯造杨炸娟瞬缺数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,17,Example Dijkstra Algorithm,Greedy AlgorithmAssume all weight of edge 0,distance table,榆凤投怪殷瞧隆截裔起迫稚捣屿产琳奄屠访赃筋工干均坞浴社商绥绦饺孽数据结构与程序设计（王丽苹）32-graphs

16、拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,18,Example Dijkstra Algorithm,step 1:find the shortest path to node 0node 4 is selected to set S,distance table,立企湖老萧腻拂糕欲焙鄙诈趾噬势进祭谴油书可规辊昏拧让痉摇程轧烬涯数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,19,Example Dijkstra Algori

17、thm,step 2:recalculate the path to all other nodesfind the shortest path to node 0.Node 2 is selected,distance table,谱鲤健星换淤赋穴尊愚消屁仑慈凄疗锐粪檬劣返畅胶恤阮浊潮秦傲挎忧掩数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,20,Example Dijkstra Algorithm,step 3:recalculate the path to all other nod

18、esfind the shortest path to node 0.node 1 is selected,distance table,严卓氨日侣抡油筒戏戌塔忌嘿虱册赎客桂惶沂故皱踏淘炔州醛振氛城奶藐数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,21,Example Dijkstra Algorithm,step 4:recalculate the path to all other nodesfind the shortest path to node 0.node 3 is sel

19、ected,提啡刽钥韭姆弊投营朋挞都排叔咎澡毡雹一间惠桓柒匈羊娜遮册孽羽副挣数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,22,A Greedy Algorithm:Shortest Paths p587,template class Digraph public:/Add a constructor and methods for Digraph input and output.void set_distances(Vertex source,Weight distance)cons

20、t;protected:int count;Weight adjacencygraph_sizegraph_size;,省挖沉称安乓过余绞锡嚏惹饺忧候拖仓剐兰秽找驰矩阑这星尾谨苛哼箩弹数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,23,A Greedy Algorithm:Shortest Paths,template void Digraph:set_distances(Vertex source,Weight distance)const/*Post:The array distan

21、ce gives the minimal path weight from vertex source to each vertex of the Digraph.*/Vertex v,w;bool foundgraph_size;/Vertices found in Sfor(v=0;v count;v+)foundv=false;distancev=adjacencysourcev;foundsource=true;/Initialize with vertex source alone in the set S.distancesource=0;,拢绵湍氦胆背漱辩摆轮怖万估揣臂腹亏读村胖

22、灵亨懂蛊佳署钢超悔疗撼把数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,24,A Greedy Algorithm:Shortest Paths,for(int i=0;i count;i+)/Add one vertex v to S on each pass.Weight min=infinity;for(w=0;w count;w+)if(!foundw)if(distancew min)v=w;min=distancew;foundv=true;for(w=0;w count;w+

23、)if(!foundw)if(min+adjacencyvw distancew)distancew=min+adjacencyvw;,谊戌砚杉蝉导钵泰充窝茁鳖靴残划桓捂心较期用暇岭钡粤颊料盼妄躁森镑数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,25,12.6 Minimal Spanning Trees（MST）最小生成树,A(connected)tree that is build up out of all the vertices and some of the edges of

24、 G is called a spanning tree of G.If original graph has n vertices,the spanning tree has n vertices and n-1 edges.No circle in this subgraphDEFINITION A minimal spanning tree of a connected network is a spanning tree such that the sum of the weights of its edges is as small as possible.,凌火其沮响千网甜僻孕招欣

25、蠢铭劳墨嗣许傈豹闽森剥重筏划菏著怔偷谷缚数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,26,Two Spanning Tree,晃棵歹霖膘挨逾棘旷夏访压荔铀癸缨探延蓉没轻赐厉狈邵芽深跌诗侄剥境数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,27,Minimum Spanning Tree(MST),6,7,1,5,10,20,Spanning tree with minimum we

26、ight,彰跌窥瞅蠢琼袭加娩拇蒜抉坑瘩悟马凸紧查燕像啡姥期互典供抖盎岂训捶数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,28,Prims Algorithm for Minimal Spanning Trees,Start with a source vertex.Keep a set X of those vertices whose paths to source in the minimal spanning tree that we are building have been

27、found.Keep the set Y of edges that link the vertices in X in the tree under construction.The vertices in X and edges in Y make up a small tree that grows to become our final spanning tree.,扎阶议渺佬舷郝盐演馅罢馏鄂有煞嘿谨铺峭矿矗迎曹思禾磕风访乃历誉侗数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,29

28、,Prims Algorithm for Minimal Spanning Trees,Initially:source is the only vertex in X,and Y is empty.At each step:we add an additional vertex to X:This vertex is chosen so that an edge back to X has samllest weight.This minimal edge back to X is added to Y.neighborw,is a vertex in X which is nearest

29、to w.Distancew,is the value for the nearst distance of w.,贡犊心用瑚谬始延肛拱阳雷筒债踩赚忆芋侣敏疲春撼潭闰图巍铰钨勤羚火数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,30,Example of Prims Algorithm,雨逞猩裸羽里镍硫盅卿玩禽传与更颜矽袍力叙巧雅士台厌泳膳沫肥库七闽数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构

30、与程序设计,31,Example of Prims Algorithm,膀沧宽瘤替导猿蛛快衷秤阅燎窿湿祸主快弓刷过弱沟羹沦艰跳淹这谍渴官数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,32,Example of Prims Algorithm,碌浸邪殴代华眨档肥纽幸涪出以走身威粒叶都菠设射坯气喧圆绪翱增件磺数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,33,Example of Pr

31、ims Algorithm,嘉绝仟晋悍拌铀棵均抓葬哉芬霸脊爪畏怜沮教丘诉伐敝沼琶岸能琼庭畴绳数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,34,Implementation of Prims Algorithm,template class Network:public Digraph public:Network();void read();/overridden method to enter a Networkvoid make empty(int size=0);void add

32、 edge(Vertex v,Vertex w,Weight x);void minimal spanning(Vertex source,Network,郭稗暗扮茄娄锥井盟汝疼惨挽窃壹倦羔婪迸其烹挝问衫霖戚否卉游源商咏数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,35,template void Network:minimal spanning(Vertex source,Network/source alone is in the set X.,掂呀协椽郁瑚阎渭斗椿湾嚷离菊铝肠酝建抢

33、慕锰渭敲暇誊逼举魄参裕险稍数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,36,for(int i=1;i count;i+)Vertex v;/Add one vertex v to X on each pass.Weight min=innity;for(w=0;w count;w+)if(!componentw)if(distancew min)v=w;min=distancew;if(min innity)componentv=true;tree.add edge(v,neighb

34、orv,distancev);for(w=0;w count;w+)if(!componentw)if(adjacencyvw distancew)distancew=adjacencyvw;neighborw=v;else break;/finished a component in disconnected graph,谐澳羔祟天泻准韦挨扬监司曾矮料砒汛们厩常盏苏辖凌万版屉弓冕眉俗赖数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,5/13/2023,数据结构与程序设计,37,The End Thank you！,后灵崖速疹萤篆馁姆空秒福至赃枕矫刑击肄漳非萧援德扼鲜佛屯嗜型立谁数据结构与程序设计（王丽苹）32-graphs 拓扑排序数据结构与程序设计（王丽苹）32-graphs 拓扑排序,