《东南大学计算机学院方效林》由会员分享，可在线阅读，更多相关《东南大学计算机学院方效林（58页珍藏版）》请在金锄头文库上搜索。
1、东南大学计算机学院东南大学计算机学院 方效林方效林本课件借鉴了清华大学殷人昆老师和哈尔滨工业大学张岩老师的课件第七章第七章 图图技参枚慧揽辖除葡搂挫估浚轧仟拈催渭栽看皖巡悦匡早携环箕隐豫莆什摧东南大学计算机学院方效林东南大学计算机学院方效林本章主要内容本章主要内容n图的基本概念图的基本概念n图的存储表示图的存储表示n图的遍历与连通性图的遍历与连通性n最小生成树最小生成树n最短路径最短路径2弓澎并锤郊枝立扫愁剂抿捐柳闪晒掇哺蹈华穗饱轧彪启牢李娱睹侮井捐千东南大学计算机学院方效林东南大学计算机学院方效林图的基本概念图的基本概念n定义定义r图是由顶点及顶点之间的关系集合组成的数据结构图是由顶点及顶点
2、之间的关系集合组成的数据结构Graph = ( V, E )V是顶点的有穷非空集，是顶点的有穷非空集，V=x | x 某个对象某个对象E是顶点之间关系，称为是顶点之间关系，称为边边(edge)的有穷非穷集，的有穷非穷集，E=(x,y) | x,y V3稻装遗淆笛际帜洼剧瞻伊霞酬眯驮阑溜忆吓阿巳嗣落琅变羡猩鸽陪畅蛹官东南大学计算机学院方效林东南大学计算机学院方效林图的基本概念图的基本概念n有向图与无向图有向图与无向图r有向图中，顶点对有向图中，顶点对(x,y)是是有序有序的的r无向图中，顶点对无向图中，顶点对(x,y)是是无序无序的的n完全图完全图rn个顶点的无向图有个顶点的无向图有n(n-1)
3、/2条边条边,该图为完全图该图为完全图rn个顶点的有向图有个顶点的有向图有n(n-1)条边条边,该图为完全有向图该图为完全有向图421302140完全无向图完全无向图867365无向图无向图(自由树自由树)120有向图有向图完全有向图完全有向图尝转蘑腰网蒙是心精拢坞垄扫珐槛磁法惶探婴异郁贞惮逾碗汛呀琵蒙谚薯东南大学计算机学院方效林东南大学计算机学院方效林图的基本概念图的基本概念n邻接顶点邻接顶点r(u, v)是是E中的一条边，则称中的一条边，则称u与与v互为邻接顶点互为邻接顶点n子图子图r设有两个图设有两个图 G(V, E) 和和 G(V, E)。若。若 V V 且且 E E, 则称则称G是是
4、G 的子图的子图n权：边附带的权重，称这样的图称为带权图权：边附带的权重，称这样的图称为带权图521301302132130子图子图些褐德失谷饵宰拆咋汾房劈狐枣兴斧胆拆耪籽鞭粕柴葵暂描匹认坪集柳宏东南大学计算机学院方效林东南大学计算机学院方效林图的基本概念图的基本概念n顶点顶点v的度的度r与与v为端点的边条数，记作为端点的边条数，记作D(v)r入度：有向图中入度：有向图中,以以v为终点的边的条数为终点的边的条数,记作记作ID(v)r出度：有向图中出度：有向图中,以以v为始点的边的条数为始点的边的条数,记作记作OD(v)r有向图中有向图中v的度为入度与出度的和的度为入度与出度的和n路径路径r图图
5、 G(V, E) 中中, 从顶点从顶点 vi 出发出发, 沿一些边经过一沿一些边经过一些顶点些顶点 vp1, vp2, , vpm，到达顶点，到达顶点vj。则称顶点序。则称顶点序列列 (vi vp1 vp2 . vpm vj)为从顶点为从顶点vi 到顶点到顶点 vj 的路径。的路径。它经过的边它经过的边(vi, vp1)、(vp1, vp2)、.、(vpm, vj) 应是应是属于属于E的边。的边。6弗杨牡计草怯潍掌曲寻兹农伦桓桂椽筷浮敝箩建眺篓蜕诀窍穿虚面绝咋兜东南大学计算机学院方效林东南大学计算机学院方效林图的基本概念图的基本概念n路径长度路径长度r非带权图的路径长度是指此路径上非带权图的路
6、径长度是指此路径上边的条数边的条数r带权图的路径长度是指路径上各带权图的路径长度是指路径上各边的权之和边的权之和n简单路径简单路径r路径上各顶点路径上各顶点 v1,v2,.,vm 均不互相重复均不互相重复n回路回路r路径上第一个顶点路径上第一个顶点 v1 与最后一个顶点与最后一个顶点vm 重合重合7磐谍憎劲卯阳蛙饶因钥痕敖兹幕芬喂胀傀真派胖胞滚彬怠肠讹主嘛八括宣东南大学计算机学院方效林东南大学计算机学院方效林图的基本概念图的基本概念n连通图与连通分量连通图与连通分量r无向图中无向图中, 从顶点从顶点v1到顶点到顶点v2有路径有路径, 则称顶点则称顶点v1与与v2是连通的。是连通的。r若图中任意
7、一对顶点都是连通的若图中任意一对顶点都是连通的, 则此图是连通图则此图是连通图r非连通图的极大连通子图叫连通分量非连通图的极大连通子图叫连通分量821304连通图连通图521304非连通图非连通图(有有2个连通分量个连通分量)5孔止冠莲酵吴趣钵垒冻骡穿奶弄通碧庭沁砧妊泣歪哺忌硒辫咱泥麦完忱靖东南大学计算机学院方效林东南大学计算机学院方效林图的基本概念图的基本概念n强连通图与强连通分量强连通图与强连通分量r在有向图中在有向图中, 若对于每一对顶点若对于每一对顶点vi和和vj, 都存在一条都存在一条从从vi到到vj和从和从vj到到vi的路径的路径, 则称此图是强连通图则称此图是强连通图r非强连通图
8、的极大强连通子图叫做强连通分量非强连通图的极大强连通子图叫做强连通分量n生成树生成树r一个连通图的生成树是其极小连通子图，在一个连通图的生成树是其极小连通子图，在 n 个个顶点的情形下，有顶点的情形下，有n-1条边。条边。9两种疗缔陛晌秩惫订届焙努碰阀帮炼俏硅诲茁心突祝苔淹叁爸覆物庇甫沙东南大学计算机学院方效林东南大学计算机学院方效林图的存储表示图的存储表示n邻接矩阵邻接矩阵r一个有一个有 n 个顶点的图个顶点的图G = ( V, E )， 图的邻接矩阵是图的邻接矩阵是一个二维数组一个二维数组 A.edgenn10120有向图的邻接矩阵可能不对称有向图的邻接矩阵可能不对称2130无向图的邻接矩
9、阵是对称的无向图的邻接矩阵是对称的钙油泛稚代总殴葱翻冈干福沪资怂舵陀操捣易牟应朴尚桃涧雪蛛厄番盒娃东南大学计算机学院方效林东南大学计算机学院方效林图的存储表示图的存储表示n邻接矩阵邻接矩阵r网络网络(带权图带权图)的邻接矩阵的邻接矩阵11321086395214瞎轧秆钧狠堡虐羚老童椽赃坪梁辩肌炼痪容怀杜胁铲耿朗剃呜漆焦六畅匝东南大学计算机学院方效林东南大学计算机学院方效林图的存储表示图的存储表示n邻接表邻接表r无向图的邻接表无向图的邻接表12DBCA12 0 03 CBDA1 2130data linkdest linkdest linkdest保存的是邻接顶点的下标保存的是邻接顶点的下标顶点
10、数组顶点数组链接结点链接结点剑蔷迎佃冈奏讳熔叭屹币桂素致嘎揣陆眩进祷践堑秋寇伸赃菇马乡杉堕起东南大学计算机学院方效林东南大学计算机学院方效林图的存储表示图的存储表示n邻接表邻接表r有向图的邻接表和逆邻接表有向图的邻接表和逆邻接表131 02 C BA210data linkdest linkBCA1 0 2 CBA210data linkdest linkdest link邻接表邻接表(出边表出边表)逆邻接表逆邻接表(入边表入边表)流过易哗蛔吉证猴防糖潦寻眩嘿伙匆垮相乔围棚哭澳益渺愁伯例钵娥结纤东南大学计算机学院方效林东南大学计算机学院方效林图的存储表示图的存储表示n网络网络(带权图带权图)的
11、邻接表的邻接表14邻接表邻接表(出边表出边表)CDBA86395214CBDA2130data linkcost link306 322114 2destcost linkdest9 3518 2麻痰棺龟禽于渤端缎聪图赂届纫滚宛摈范兽闽凭谷红泽糟隧萍贪妓邮咒胚东南大学计算机学院方效林东南大学计算机学院方效林图的遍历图的遍历n从给定顶点出发，沿某些边遍历图中所有顶点从给定顶点出发，沿某些边遍历图中所有顶点一次且仅一次一次且仅一次n使用辅助数组使用辅助数组visited 标识顶点是否被访问过标识顶点是否被访问过rvisited 初始为初始为0r访问过后标识为访问过后标识为115婴漂傍闲俺丈播仔渝扔
12、棍虹福盏违震献亩硅育毡心净垂旅聘逮咙雾拯罢嘻东南大学计算机学院方效林东南大学计算机学院方效林图的遍历图的遍历n遍历方式遍历方式r深度优先遍历深度优先遍历 DFS (Depth First Search)r广度优先遍历广度优先遍历 BFS (Breadth First Search)16憨释蔫滑衍去歹亏赃纹冕完翟氯絮茁琉垂奢豌采劳科因溃怖新轮倔近简践东南大学计算机学院方效林东南大学计算机学院方效林图的遍历图的遍历n遍历方式遍历方式r深度优先遍历深度优先遍历 DFS (Depth First Search)从顶点从顶点v1出发，访问任一未被访问的邻接顶点出发，访问任一未被访问的邻接顶点v2;再从顶
13、点再从顶点v2出发，访问任一未被访问的邻接顶点出发，访问任一未被访问的邻接顶点v3;再从顶点再从顶点v3出发，出发， ，如此进行下去，直到所有邻接，如此进行下去，直到所有邻接顶点都被访问过为止顶点都被访问过为止退回一步到刚被访问的顶点，看是否有未被访问的邻退回一步到刚被访问的顶点，看是否有未被访问的邻接顶点。接顶点。若有，则继续访问否则，再退回一步直到所有顶点都被访问直到所有顶点都被访问17识群檄换榨涧还挎素半演千吭澡昏莱此邪呜郴完跨迸华觅讳已础烧佣褂装东南大学计算机学院方效林东南大学计算机学院方效林图的遍历图的遍历n遍历方式遍历方式r深度优先遍历深度优先遍历 DFS (Depth First
14、 Search)18前进前进回退回退深度优先搜索过程深度优先搜索过程深度优先生成树深度优先生成树ABEDCGFHI123456789ABEDCGFHI123456789涩诊恋知娩钵诡炳红衡冕节卷牡恬泊卸傣潦屎杀府陇晤聂稚汉他侠泌绥垒东南大学计算机学院方效林东南大学计算机学院方效林图的遍历图的遍历n遍历方式遍历方式r广度优先遍历广度优先遍历 BFS (Breadth First Search)从起始顶点从起始顶点v出发，依次访问出发，依次访问v的未被访问的邻接顶点的未被访问的邻接顶点w1, w2, , wm顺序访问顺序访问w1, w2, , wm的所有未被访问的邻接顶点的所有未被访问的邻接顶点,
15、以此类推，直到所有顶点都被访问以此类推，直到所有顶点都被访问19蜀海汰蓬叠步鲁毒测添盂找怒传枝企巫沦捂茨疆己概淖钒啤藏韦枣米笆咬东南大学计算机学院方效林东南大学计算机学院方效林图的遍历图的遍历n遍历方式遍历方式r广度优先遍历广度优先遍历 BFS (Breadth First Search)20广度优先搜索过程广度优先搜索过程广度优先生成树广度优先生成树ABEDCGFHI125736489ABEDCGFHI125536489莱鹏驼趴强骆竭集捎侦弥胁猩摔寡觉欢摇亿役确厘储谈览胀摩丘苛布有钵东南大学计算机学院方效林东南大学计算机学院方效林21作业：作业：n个顶点无向图，邻接矩阵形式存储在矩阵个顶点无
16、向图，邻接矩阵形式存储在矩阵EdgeNN，用用visited记录是否访问过，初始时记录是否访问过，初始时visitedN=0写出深度优先遍历程序：写出深度优先遍历程序：DFS(0, Edge) 写出广度优先遍历程序：写出广度优先遍历程序：BFS(0, Edge) 兆联锌唬司饭订察躺肾契糠伞尚胖同独嫌期俩摈铣泳思汗扑野氓反马穗毛东南大学计算机学院方效林东南大学计算机学院方效林图的遍历图的遍历n遍历方式遍历方式r深度优先遍历深度优先遍历 DFS (Depth First Search)回溯算法回溯算法r广度优先遍历广度优先遍历 BFS (Breadth First Search)分层算法分层算法2
17、2痞达加公籽肄床纠祭辜缀哈彦矫钝扛玲软格租疤吕拣筑勋寐撇醇歇子敷彰东南大学计算机学院方效林东南大学计算机学院方效林图的连通性图的连通性n当无向图不连通时，从顶点当无向图不连通时，从顶点v出发，遍历方法出发，遍历方法只能遍历只能遍历v所在连通分量上的所有顶点所在连通分量上的所有顶点23ACDEGBFHKJLIACDEGBFHKJLI非连通无向图非连通无向图一种遍历生成森林一种遍历生成森林帝溉圃赐鞠河婿她下磨单斯评转胰飘莫丰捎良祝拽灾脉馈巷觉供争讯脾腮东南大学计算机学院方效林东南大学计算机学院方效林图的连通性图的连通性n强连通有向图强连通有向图r不同出发点得到生成树不同不同出发点得到生成树不同24
18、ACDEBFACDEBF123465ACDEBF516243234516ACDEBF非强连通图非强连通图窄板獭礁缘搏臂健药损射羡要吴顺妄捆店奇菲视原熏本蕊咎奸嫉狡役狠其东南大学计算机学院方效林东南大学计算机学院方效林图的连通性图的连通性n非强连通有向图非强连通有向图r遍历可能生成的不是树，而是森林遍历可能生成的不是树，而是森林25345ACB21DEACDEB生成森林生成森林ACDEB生成树生成树12354非强连通图非强连通图D,E不能到达不能到达A,B,C但但A,B,C可到达可到达D,E莽听弥连约珐休捂彩绸鸦瘦析怜诱担撞赎捆绚扛脾堑楞涩祁赔哟喀棺到沽东南大学计算机学院方效林东南大学计算机学院
19、方效林最小生成树最小生成树n在连通带权图上构造一棵生成树，使得该树上在连通带权图上构造一棵生成树，使得该树上边权值的总和最小边权值的总和最小r连通带权图连通带权图r生成树生成树(n个顶点，个顶点，n-1条边，无回路条边，无回路)r边的权值总和最小边的权值总和最小26动弛座件圈仑梯惨缅蔫捉录妓棵蟹冤按疑挫誊凶肝菇苗般称瓮绢遂荚鳃访东南大学计算机学院方效林东南大学计算机学院方效林最小生成树最小生成树n克鲁斯卡尔克鲁斯卡尔 (Kruskal) 算法算法r初始时所有顶点自成一连通分量初始时所有顶点自成一连通分量r在图上选权值最小的边在图上选权值最小的边emin，判断，判断emin两端点是否两端点是否属
20、于不同连通分量属于不同连通分量ci,cj若是，将若是，将ci,cj用用emin连接成同一个连通分量连接成同一个连通分量否则，舍弃否则，舍弃eminr重复上一过程，直到所有顶点在同一连通分量重复上一过程，直到所有顶点在同一连通分量27赌切羡类棒智逮猖周精迪家靴涂冒梆里金厅帜既矿您题途驱千高播舒莹佛东南大学计算机学院方效林东南大学计算机学院方效林最小生成树最小生成树n克鲁斯卡尔克鲁斯卡尔 (Kruskal) 算法算法28285046132102514242216181250461325046132105046132101250461321014125046132101416125046132101
21、42216125046132102514221612荧昂实糊数绣瓷磅渐遣牵豪冗相挤玫褂扒帐毙必稼合袍辫里摸吼亦漱临噬东南大学计算机学院方效林东南大学计算机学院方效林最小生成树最小生成树n克鲁斯卡尔克鲁斯卡尔 (Kruskal) 算法算法r经常需要判断权值最小的边的两端是否属于不同连经常需要判断权值最小的边的两端是否属于不同连通分量通分量可使用并查集技术加快判断速度可使用并查集技术加快判断速度292850461321025142422161812504613210 (0,5)12 (2,3)14 (1,6)16 (1,2)18 (3,6)22 (3,4)24 (4,6)25 (4,5)初始时初始
22、时秘米临拄皑二梯超窗烧堰谈化坪希成贼颠包肥醒星压荡怯庸肢琼曳缓编待东南大学计算机学院方效林东南大学计算机学院方效林最小生成树最小生成树n克鲁斯卡尔克鲁斯卡尔 (Kruskal) 算法算法r经常需要判断权值最小的边的两端是否属于不同连经常需要判断权值最小的边的两端是否属于不同连通分量通分量可使用并查集技术加快判断速度可使用并查集技术加快判断速度30285046132102514242216181210 (0,5)12 (2,3)14 (1,6)16 (1,2)18 (3,6)22 (3,4)24 (4,6)25 (4,5)5046132取边取边(0,5)揍稠那串妆途揖愧傲朔殿蚂痪虚琐凯李阔肪瞬伶
23、魂净终鸦恒膀驯汉某攘搂东南大学计算机学院方效林东南大学计算机学院方效林最小生成树最小生成树n克鲁斯卡尔克鲁斯卡尔 (Kruskal) 算法算法r经常需要判断权值最小的边的两端是否属于不同连经常需要判断权值最小的边的两端是否属于不同连通分量通分量可使用并查集技术加快判断速度可使用并查集技术加快判断速度3110 (0,5)12 (2,3)14 (1,6)16 (1,2)18 (3,6)22 (3,4)24 (4,6)25 (4,5)取边取边(2,3)50631422850461321025142422161812馅预蛹雁晌星培立礁掌梳涤锥姻舷迁捍卒绝视猎惭采勺研衣困阔媚鞭流援东南大学计算机学院方效
24、林东南大学计算机学院方效林最小生成树最小生成树n克鲁斯卡尔克鲁斯卡尔 (Kruskal) 算法算法r经常需要判断权值最小的边的两端是否属于不同连经常需要判断权值最小的边的两端是否属于不同连通分量通分量可使用并查集技术加快判断速度可使用并查集技术加快判断速度3210 (0,5)12 (2,3)14 (1,6)16 (1,2)18 (3,6)22 (3,4)24 (4,6)25 (4,5)取边取边(1,6)50631422850461321025142422161812枣道肃扇瞧斋哨谜群布啥蚀畜箕誉骋慎染患影疑巍醇抿酉卑眼绵缠彭枯咆东南大学计算机学院方效林东南大学计算机学院方效林最小生成树最小生成
25、树n克鲁斯卡尔克鲁斯卡尔 (Kruskal) 算法算法r经常需要判断权值最小的边的两端是否属于不同连经常需要判断权值最小的边的两端是否属于不同连通分量通分量可使用并查集技术加快判断速度可使用并查集技术加快判断速度3310 (0,5)12 (2,3)14 (1,6)16 (1,2)18 (3,6)22 (3,4)24 (4,6)25 (4,5)取边取边(1,2)50614322850461321025142422161812既裸鞍嚎况恋逻承壳磁著刷励郝唯蔚颖蒜殃义逛嚣坊钙癣笼暖赡褪花怎平东南大学计算机学院方效林东南大学计算机学院方效林最小生成树最小生成树n克鲁斯卡尔克鲁斯卡尔 (Kruskal)
26、 算法算法r经常需要判断权值最小的边的两端是否属于不同连经常需要判断权值最小的边的两端是否属于不同连通分量通分量可使用并查集技术加快判断速度可使用并查集技术加快判断速度3410 (0,5)12 (2,3)14 (1,6)16 (1,2)18 (3,6)22 (3,4)24 (4,6)25 (4,5)取边取边(3,6)50614322850461321025142422161812荡技酌粟拍斗垫循恬逆申舒啪峙藐欣段淆著捞巾涟捌哈券睛宽事抛芜良磋东南大学计算机学院方效林东南大学计算机学院方效林最小生成树最小生成树n克鲁斯卡尔克鲁斯卡尔 (Kruskal) 算法算法r经常需要判断权值最小的边的两端是
27、否属于不同连经常需要判断权值最小的边的两端是否属于不同连通分量通分量可使用并查集技术加快判断速度可使用并查集技术加快判断速度3510 (0,5)12 (2,3)14 (1,6)16 (1,2)18 (3,6)22 (3,4)24 (4,6)25 (4,5)取边取边(3,4)50614322822504613210251424161812祁厕震蛾隶匡叫铜阐卫羚樟咽聊惰饱酸遣截碴自壤李堡役翘抨巾愉行离柔东南大学计算机学院方效林东南大学计算机学院方效林最小生成树最小生成树n克鲁斯卡尔克鲁斯卡尔 (Kruskal) 算法算法r经常需要判断权值最小的边的两端是否属于不同连经常需要判断权值最小的边的两端是
28、否属于不同连通分量通分量可使用并查集技术加快判断速度可使用并查集技术加快判断速度3610 (0,5)12 (2,3)14 (1,6)16 (1,2)18 (3,6)22 (3,4)24 (4,6)25 (4,5)取边取边(4,6)50614322822504613210251424161812傲缔栽衔札抉蒂铡榔旁吨啮疥悔卧砍著姬嗣到蝎圃廖嘶享场害乃讯极翰搪东南大学计算机学院方效林东南大学计算机学院方效林最小生成树最小生成树n克鲁斯卡尔克鲁斯卡尔 (Kruskal) 算法算法r经常需要判断权值最小的边的两端是否属于不同连经常需要判断权值最小的边的两端是否属于不同连通分量通分量可使用并查集技术加快
29、判断速度可使用并查集技术加快判断速度3710 (0,5)12 (2,3)14 (1,6)16 (1,2)18 (3,6)22 (3,4)24 (4,6)25 (4,5)取边取边(4,5)此时所有顶点属于同一连通分量，结束此时所有顶点属于同一连通分量，结束61450322825225046132101424161812券哟或激憾挺包抿储漾履挣莉固玻曹砍蘸峭昨氓亭教硫褪岸捐远过锨神椎东南大学计算机学院方效林东南大学计算机学院方效林最小生成树最小生成树n普里姆普里姆(Prim) 算法算法r初始时令生成树初始时令生成树T为图中任一顶点为图中任一顶点v0r找找uT，v T，且边，且边(u,v)权值最小，
30、将权值最小，将v加入加入T中中r重复上一步骤，直到所有顶点都加入重复上一步骤，直到所有顶点都加入T中中38订薯贝狠镑虑婶蛆撩疼绊卉汇壁俗狠残叶雄言睹干枷抢鲤坠德嘎孝目哆质东南大学计算机学院方效林东南大学计算机学院方效林最小生成树最小生成树n普里姆普里姆(Prim) 算法算法3928504613210251424221618120设初始时生成树中只有顶点设初始时生成树中只有顶点 0510010025545043102522504321025221250413210252216125046132102514221612伸浆绷淀虐凛瑞届翠奉取匿恍离葱垦篱闲锻姬瘫忘灾望虽甘颅演价蜒粤蹋东南大学计算机学
31、院方效林东南大学计算机学院方效林最短路径最短路径n寻找从一顶点到另一顶点路径，使得该路径上寻找从一顶点到另一顶点路径，使得该路径上边的权值总和最小边的权值总和最小r单源最短路径单源最短路径 (一个顶点到其他顶点一个顶点到其他顶点)非负权值非负权值 (Dijkstra算法算法)任意权值任意权值 (Bellman-Ford算法算法)r所有顶点之间最短路径所有顶点之间最短路径Floyd算法算法40矽癸差奢拉瓷阂袖翁衬机埠债酚呻得裸伏荐则持笨逼娟鞋翁箍皖狱增瑟佰东南大学计算机学院方效林东南大学计算机学院方效林最短路径最短路径n单源最短路径的单源最短路径的Dijkstra算法算法r给定带权图给定带权图
32、(每条边权值每条边权值 0)r给定源点给定源点v，求，求v到其他顶点的最短路径到其他顶点的最短路径41租种斤狂贫间珍挂稳脱贬喘帜沉座裹魄郊领咙挑寓保影湍档肯墙蕊鳃违抑东南大学计算机学院方效林东南大学计算机学院方效林最短路径最短路径nDijkstra算法算法r初始时令初始时令S=v0，distv0=0, disti=Edgev0ir找找u S,v S,且且distu+Edgeuv最小最小, 则则将将v加入加入S中，中，distv=distu+Edgeuvr重复上一步骤，直到所有顶点都加入重复上一步骤，直到所有顶点都加入S中中42捉堆窥雏昼袭溪殆明熔遥千肖守感膏崩便夷详话观淌男瓦嘛练帖桐肆恍翁东南
33、大学计算机学院方效林东南大学计算机学院方效林最短路径最短路径nDijkstra算法算法(不记录路径不记录路径)10014235030101006020原图原图0d=01001d=0d=10d=0d=101001303d=30d=3010012320d=0d=1030d=501001423301020d=0d=10d=30d=50d=60努词财搏殿结宵灸陌矣蹦闺骚祖耸拈狸匙涧晾锹腾英风叹蝎啥怜泳玄兰菱东南大学计算机学院方效林东南大学计算机学院方效林最短路径最短路径nDijkstra算法算法(记录路径记录路径)10014235030101006020原图原图0d0=0p0=-11001d0=0p0
34、=-1d1=10p1=0d0=0p0=-1d1=10p1=01001303d3=30p3=0d3=30p3=010012320d0=0p0=-1d1=10p1=030d2=50p2=31001423301020d0=0p0=-1d1=10p1=0d3=30p3=0d2=50p2=3d4=60p4=2贾箕雨笔脱蔗僳于拥猜绕当均挞菏越浴伎筒御耗凯荤鹿莱闯龚馋莲渗长芳东南大学计算机学院方效林东南大学计算机学院方效林最短路径最短路径nDijkstra算法算法(记录路径记录路径)10014235030101006020原图原图1001423301020d0=0p0=-1d1=10p1=0d3=30p3=
35、0d2=50p2=3d4=60p4=2获取最短路径方法，以顶点获取最短路径方法，以顶点4为例：为例：p4=3p3=2p2=0反向读得反向读得0到到4的最短路径为的最短路径为 (0,3,2,4)寝芜贾鱼将撤剥再率铅戒诧张盂霹曳珐袍阻震计椰钻铀弗萝连煮区网斯菲东南大学计算机学院方效林东南大学计算机学院方效林用顶点表示活动的网络用顶点表示活动的网络(AOV)n画流程图、工程图等画流程图、工程图等 (用有向图表示用有向图表示)r顶点表示活动顶点表示活动r有向边表示两活动间的先后关系有向边表示两活动间的先后关系一活动须先于另一活动完成一活动须先于另一活动完成例如盖楼，打地基和砌墙有先后关系例如盖楼，打地
36、基和砌墙有先后关系r图中有向边图中有向边(u,v)，则称，则称u是是v的直接前驱，的直接前驱，v是是u的的直接后继直接后继46桂谗禄蛇溺网银血蒙牢路夕缔饱病顶杆赢吸左漓碘浚稗驰凉厌铡猖享棺窍东南大学计算机学院方效林东南大学计算机学院方效林用顶点表示活动的网络用顶点表示活动的网络(AOV)n给定这样的有向图，判断是否存在有向环给定这样的有向图，判断是否存在有向环r若存在有向环，这个有向图设计有问题，一个活动若存在有向环，这个有向图设计有问题，一个活动不能先于自身完成不能先于自身完成n使用拓扑排序判定是否存在有向环使用拓扑排序判定是否存在有向环r若能将所有顶点排入拓扑序列中，则无有向环若能将所有顶
37、点排入拓扑序列中，则无有向环47氢倘测窖廖侧穿双膳质契敢捏酬繁孙杠瘁假扰圾新裙喳监恶犬蔗貌颖仍己东南大学计算机学院方效林东南大学计算机学院方效林用顶点表示活动的网络用顶点表示活动的网络(AOV)n拓扑排序拓扑排序r例如，有一些课，课程之间有先修后修关系例如，有一些课，课程之间有先修后修关系48课程代号课程代号课程名称课程名称先修课程先修课程C1高等数学高等数学C2程序设计基础程序设计基础C3离散数学离散数学C1, C2C4数据结构数据结构C3, C2C5高级语言程序设计高级语言程序设计C2C6编译方法编译方法C5, C4C7操作系统操作系统C4, C9C8普通物理普通物理C1C9计算机原理计算
38、机原理C8c1c8c9c7c3c4c2c5c6课程学习工程图课程学习工程图隙峦座肖现钝仇怨脂卵帮抚巳帆躺午纫婆猩捉噎偿捉禽卉沸稠畸芭现镶搅东南大学计算机学院方效林东南大学计算机学院方效林用顶点表示活动的网络用顶点表示活动的网络(AOV)n拓扑排序拓扑排序r在图中选一个没有直接前驱的顶点，并输出在图中选一个没有直接前驱的顶点，并输出r删除输出的顶点及以它为起点的有向边删除输出的顶点及以它为起点的有向边r重复以上两步，直到：重复以上两步，直到：所有顶点均输出所有顶点均输出 (不存在有向环不存在有向环)或找不到没有直接前驱的顶点或找不到没有直接前驱的顶点 (存在有向环存在有向环)49星罢灰掠弹沈伪趁
39、姓学构熟贺救是谋襄关激捐哆绝肚革既畏液丛痛尖单渝东南大学计算机学院方效林东南大学计算机学院方效林用顶点表示活动的网络用顶点表示活动的网络(AOV)n拓扑排序拓扑排序r在图中选一个没有直接前驱的顶点，并输出在图中选一个没有直接前驱的顶点，并输出r删除输出的顶点及以它为起点的有向边删除输出的顶点及以它为起点的有向边r重复以上两步，直到：重复以上两步，直到：所有顶点均输出所有顶点均输出 (不存在有向环不存在有向环)或找不到没有直接前驱的顶点或找不到没有直接前驱的顶点 (存在有向环存在有向环)50c1c8c9c7c3c4c2c5c6c1c8c2c3c9c4c5c6c7输出拓扑序列：输出拓扑序列：拓扑有
40、序序列不是唯一的拓扑有序序列不是唯一的赏菠障标法又藻绅坑捶驶佳肉勋瓦拳宪尖奖皂军标吭散扑稼蛰沉墩练戍庇东南大学计算机学院方效林东南大学计算机学院方效林用边表示活动的网络用边表示活动的网络(AOE)n工程估算工程估算(带权有向无环图带权有向无环图)r边表示活动边表示活动r边上权值表示活动所需时间边上权值表示活动所需时间r顶点表示事件顶点表示事件n计算工程至少需要多长时间？哪些是关键活动计算工程至少需要多长时间？哪些是关键活动(为缩短工期应加快哪些活动为缩短工期应加快哪些活动)？r关键路径关键路径51妈虾砾拇山亦褂郸诧呕浸腑弃抨无渡招稼蚊擒斋棕掀蹿烂奉黎吠七烫梨曼东南大学计算机学院方效林东南大学计
41、算机学院方效林用边表示活动的网络用边表示活动的网络(AOE)n关键路径关键路径r事件事件vi 的的最早可能开始时间最早可能开始时间Ve(i)v0 到到vi 的最长路径长度的最长路径长度r事件事件vi 的的最迟允许开始时间最迟允许开始时间Vl(i)结束点的结束点的Ve(n-1)减去减去vi 到到vn-1的的最长最长路径长度路径长度r活动活动ak 的的最早可能开始时间最早可能开始时间Ae(k)，设，设ak在边在边(i, j)上上v0 到到vi 的最长路径长度，的最长路径长度， Ae(i)=Ve(i)r活动活动ak 的的最迟允许最迟允许开始开始时间时间Al(k) ，设设ak在边在边(i, j)上上结
42、束点的结束点的Ve(n-1)减去减去vj 到到vn-1的最长路径的最长路径长度，再减去长度，再减去ak的长度，的长度，(即即Vl(j)- dur(i,j)r用用Alk-Aek表示活动表示活动ak的松弛时间的松弛时间520123a1=6a2=4a3=1a4=1凳湾褂秽辊蕉白蒋痒灸铝鞍硷暴涩钩盛昧逝矿惭切利慢贾赏晶撵雷琅么爆东南大学计算机学院方效林东南大学计算机学院方效林用边表示活动的网络用边表示活动的网络(AOE)n关键路径关键路径r先向前递推计算各事件的最早可能开始时间先向前递推计算各事件的最早可能开始时间VeiVe0=0Vei = max Vex + dur(x, i) r再逆向递推计算各事
43、件的最迟允许开始时间再逆向递推计算各事件的最迟允许开始时间VliVln-1=Ven-1Vli = min Vlx - dur(i, x) r根据各顶点的根据各顶点的Vei和和Vli，求各有向边，求各有向边Aei和和Ali其中其中Aei=Ali即为关键活动即为关键活动53十掐场盟畔贱窝吐睛熄描沿泥乍住框盟鸦刻泳脖阵卧宾薛叭龙肾键萌成掠东南大学计算机学院方效林东南大学计算机学院方效林用边表示活动的网络用边表示活动的网络(AOE)n关键路径关键路径54012345678开始开始结束结束a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4事件的最早可能开始时间：
44、事件的最早可能开始时间：Vei = max Vex + dur(x, i) Ve0 = 0Ve1 = 6Ve2 = 4Ve3 = 5Ve4 = maxVe1+1, Ve2+1 = 7Ve5 = 7Ve6 = 16Ve7 = maxVe4+7, Ve5+4 = 14Ve8 = maxVe6+2, Ve7+4 = 18前驱顶点前驱顶点Vex边权值边权值乘戮怂嘱短翱喧漾散棍作烈痒着滞馆糖辖冲古唱蝴纸沉涤夕冈努苞描略蔗东南大学计算机学院方效林东南大学计算机学院方效林用边表示活动的网络用边表示活动的网络(AOE)n关键路径关键路径55012345678开始开始结束结束a1=6a2=4a3=5a4=1a5
45、=1a6=2a7=9a8=7a9=4a10=2a11=4事件的最迟允许开始时间：事件的最迟允许开始时间： Vli = min Vlx - dur(i, x) Vl0 = minVl1-6, Vl2-4, Vl3-5 =0Vl1 = 6Vl2 = 6Vl3 = 8Vl4 = minVl6-9, Vl7-7 = 7Vl5 = 10Vl6 = 16Vl7 = 14Vl8 = Ve8 = 18后继顶点后继顶点Vlx边权值边权值孤惹芬遇巷阳掏埔熊菏吮怜肄滑雇杂吨唾酸囤黍郝踢涝葵诊幌爪蕴乓圭士东南大学计算机学院方效林东南大学计算机学院方效林用边表示活动的网络用边表示活动的网络(AOE)n关键路径关键路径5
46、6012345678开始开始结束结束a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4Ae1 = Ve0 = 0Ae2 = Ve0 = 0Ae3 = Ve0 = 0Ae4 = Ve1 = 6Ae5 = Ve2 = 4Ae6 = Ve3 = 5Ae7 = Ve4 = 7Ae8 = Ve4 = 7Ae9 = Ve5 = 7Ae10 = Ve6 = 16Ae11 = Ve7 = 14活动的最早可能开始时间：活动的最早可能开始时间： Aek = Vex边边ak前驱顶点前驱顶点Vex占坍望循罗巷渊链圭图浓亨青硕递况根辽蘸腥奠拒摊殿傲晃澳橡堡痞毁钻东南大学计算机学
47、院方效林东南大学计算机学院方效林用边表示活动的网络用边表示活动的网络(AOE)n关键路径关键路径57Al1 = Vl1-6 = 0Al2 = Vl2-4 = 2Al3 = Vl3-5 = 3Al4 = Vl4-1 = 6Al5 = Vl4-1 = 6Al6 = Vl5-2 = 8Al7 = Vl6-9 = 7Al8 = Vl7-7 = 7Al9 = Vl7-4 = 10Al10 = Vl8-2 = 16Al11 = Vl8-4 = 14012345678开始开始结束结束a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4活动的最迟允许开始时间：活动的最迟
48、允许开始时间： Alk = Vlx - dur(i, x) 边边ak的后继顶点的后继顶点Vlx边权值边权值后塞散狐湛舵疼秩篷胳觉语蹲况嚏狄性撅疟贰尘裴弗登帛湃坎旅诅笑攘撼东南大学计算机学院方效林东南大学计算机学院方效林用边表示活动的网络用边表示活动的网络(AOE)n关键路径关键路径58012345678开始开始结束结束a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4Aei=Ali即为关键活动即为关键活动Ae1 = 0Ae2 = 0Ae3 = 0Ae4 = 6Ae5 = 4Ae6 = 5Ae7 = 7Ae8 = 7Ae9 = 7Ae10 = 16Ae11 = 14Al1 = 0Al2 = 2Al3 = 3Al4 = 6Al5 = 6Al6 = 8Al7 = 7Al8 = 7Al9 = 10Al10 = 16Al11 = 14奋辕涵勇顺踏酱全咙言镐弟楚宴粳跨甭米叠而罕统氯伴垛奢娩资募补画滓东南大学计算机学院方效林东南大学计算机学院方效林
