《图及其应用(new)》由会员分享，可在线阅读，更多相关《图及其应用(new)（204页珍藏版）》请在金锄头文库上搜索。
1、第第10章章 图及其应用图及其应用 110.1 图的概念 10.2 图的存储 10.3 图的遍历 10.4 生成树和最小生成树 10.5 最短路径 10.6 有向无环图的应用第10章 图及其应用陶奋摔等绣臼鄂慨窟忠健站避洛返敦甘俯圾铺累嘲悼奉穆摇草沏润圈瞧关图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 2 图图图图(Graph)(Graph)：是一种网状数据结构。是顶点集：是一种网状数据结构。是顶点集V和连和连接这些顶点的弧集接这些顶点的弧集(边集边集)VR所组成的结构记为所组成的结构记为 : G=(V,VR）有向图：有向图：有向图：有向图：若若图中的边是顶点的有
2、序对图中的边是顶点的有序对图中的边是顶点的有序对图中的边是顶点的有序对, 则称此图为则称此图为有向图。有向图。 有向边又称为弧有向边又称为弧有向边又称为弧有向边又称为弧, 通常用尖括弧表示一条有向通常用尖括弧表示一条有向边边, vi, vj表示从顶点表示从顶点vi到到vj的一段弧的一段弧, vi称为边的始称为边的始点点(或弧尾或弧尾), vj称为边的终点称为边的终点(或弧头或弧头), vi,vj和和 vj, vi代表两条不同的弧。代表两条不同的弧。132删竖痴穆珠洞肋轧尊腕瓢关撇复观骇荆砰鹊东骇埂叛甲蜡茬萌蕴波旷窘盗图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 3
3、无无无无向向向向图图图图：若若图图图图中中中中的的的的边边边边是是是是顶顶顶顶点点点点的的的的无无无无序序序序对对对对, 则则称称此此图图为无向图。为无向图。 通通常常用用圆圆圆圆括括括括号号号号表表表表示示示示无无无无向向向向边边边边, , (vi, vj)表表示示顶顶点点vi和和vj间间相相连连的的边边。在在无无向向图图中中(vi, vj)和和(vj, vi)表表示示同同一一条条边边.2341贤撰悸泣均臭掌绿吐燃态甄吁阐读峡部坦罚寺菌莉贰梗试颜教忿欧盖回小图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 4完全图、稠密图、稀疏图完全图、稠密图、稀疏图完全图、稠密图
4、、稀疏图完全图、稠密图、稀疏图 具具有有n个个顶顶点点，n(n-1)/2条条边边的的图图，称称为为完完完完全全全全无无无无向向向向图图图图，具具有有n个个顶顶点点，n(n-1) 条条弧弧的的有有向向图图,称称为为完完完完全全全全有有有有向向向向图图图图。完全无向图和完全有向图都称为完全无向图和完全有向图都称为完全图完全图完全图完全图。 对对于于一一般般无无向向图图，顶顶点点数数为为n，边边数数为为e，则则 0e n(n-1)/2。 对对于于一一般般有有向向图图，顶顶点点数数为为n，弧弧数数为为e， 则则 0en(n-1) 。 当当一一个个图图接接近近完完全全图图时时，则则称称它它为为稠稠稠稠密
5、密密密图图图图，相相反反地地，当一个图中含有较少的边或弧时，则称它为当一个图中含有较少的边或弧时，则称它为稀疏图稀疏图稀疏图稀疏图。讯拽急总抒栓休衬垒镍焉喀巩剖额盖颤鄂涛渴爹技糠口湛卸瑰磺吟驯日民图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 5子图：子图：子图：子图：对于图对于图G=(V, VR),G=(V,VR),若有若有V V, VR VR, 则称图则称图G是是G的一个子图。的一个子图。 下图给出了下图给出了G与其子图与其子图G 。 2435167图G435167图G 堕汹顺恒矢澡台启圣稼牡字郸旺谢酬蹬饲奋教画莹徘账肆味怀您隙萝驴耘图及其应用(new)图及其应
6、用(new)第第10章章 图及其应用图及其应用 6邻接点邻接点邻接点邻接点 对对于于无无无无向向向向图图图图 G=(V, VR)，如如如如果果果果边边边边(v(v，v)v)VRVR， 则则则则称称称称顶顶顶顶点点点点v, v, vv互互互互为为为为邻邻邻邻接接接接点点点点，即即v, v相相邻邻接接。边边（v, v）依依附附于于顶顶点点v和和v，或或者者说说边边（v， v）与与顶顶点点v和和v相相关关联。联。 对对于于有有有有向向向向图图图图G=(V，VR)而而言言，若若若若弧弧弧弧vvVRVR， 则则则则称称称称顶顶顶顶点点点点v v邻邻邻邻接接接接到到到到顶顶顶顶点点点点vv，顶顶顶顶点点点
7、点vv邻邻邻邻接接接接自自自自顶顶顶顶点点点点v v，或或者者说说弧弧与顶点与顶点v和和v相关联。相关联。 2341132如：顶点如：顶点1、2互为邻接点互为邻接点如：顶点如：顶点1邻接到顶点邻接到顶点2 顶点顶点2邻接自顶点邻接自顶点1懂瓤慨挞甜侥仅卞春禾酿铭隅甥封柞瓜郧羡秤涉氖椰闰峰某彩铱蛇淋逆眩图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 7权与网权与网权与网权与网 在在实实际际应应用用中中，图图的的边边或或弧弧上上往往往往与与具具有有一一定定意意义义的的数数有有关关，即即每每每每一一一一条条条条边边边边都都都都有有有有与与与与它它它它相相相相关关关关的的的
8、的数数数数，称称为为权权权权，我们将我们将这种带权的图这种带权的图这种带权的图这种带权的图叫做叫做赋权图赋权图赋权图赋权图或或网网网网，如图所示。，如图所示。 涯叼拜障锋嘘渐抽佃纤峨雨茸苇肥磅晕俏族矣希翱醛字七苗峙姚妹溉与肩图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 8路径和回路路径和回路路径和回路路径和回路路径：路径：路径：路径：所谓顶点所谓顶点vp 到顶点到顶点vq之间的路径之间的路径, 是指是指顶点序列顶点序列顶点序列顶点序列vp, vi1 , vi2 , , vim, vq, 其中（其中（ vp,vi1）, （ vi1 , vi2）, （ vim, vq
9、 ）分别为图中的边。）分别为图中的边。 路径长度：路径上边的数目路径长度：路径上边的数目路径长度：路径上边的数目路径长度：路径上边的数目称为路径长度。称为路径长度。 简单路径：简单路径：简单路径：简单路径：序列中序列中顶点不重复出现的路径顶点不重复出现的路径顶点不重复出现的路径顶点不重复出现的路径称为简单路径。称为简单路径。回路或环：回路或环：回路或环：回路或环：如果如果路径的起点和终点相同路径的起点和终点相同路径的起点和终点相同路径的起点和终点相同(即即vp = vq), 则则称此路径为回路或环。称此路径为回路或环。眺羽纶厦痈十献队钳埔蘸昭捎摆扑省坦肉府蝶噎毅豌乎丰袖龟兴琢各缺惺图及其应用(
10、new)图及其应用(new)第第10章章 图及其应用图及其应用 9 如图所示的无向图中如图所示的无向图中, 顶点顶点顶点顶点v1v1到顶点到顶点到顶点到顶点v5v5的路径有两条的路径有两条的路径有两条的路径有两条, 分别为分别为v1, v2, v3, v4与与v1, v5, v4, 路径长度分别为路径长度分别为路径长度分别为路径长度分别为3 3和和和和2 2。 v1到到v5的两条路径都为的两条路径都为简简简简单路径单路径单路径单路径。简单回路：简单回路：简单回路：简单回路：除第一顶点与最后一个顶点之外除第一顶点与最后一个顶点之外除第一顶点与最后一个顶点之外除第一顶点与最后一个顶点之外, , 其
11、它顶点不其它顶点不其它顶点不其它顶点不重复出现的回路重复出现的回路重复出现的回路重复出现的回路为简单回路或者简单环。为简单回路或者简单环。 寝烙痔妓百薯蓝哮邯莉渗矽炉恬斩锯既川诲斟久疼谍辫腔尚晰羞游愁翁年图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 10 连通图和强连通图连通图和强连通图连通图和强连通图连通图和强连通图 在在无向图无向图无向图无向图中，若从顶点中，若从顶点i到顶点到顶点j有路径，则称顶点有路径，则称顶点i和顶点和顶点j是连通的。若任意两个顶点都是连通的，则称是连通的。若任意两个顶点都是连通的，则称此无向图为连通图，否则称为非连通图。此无向图为连通图
12、，否则称为非连通图。 连通图和非连通图示例见图连通图和非连通图示例见图: 瘩余唉业鞋蹄区蹈儿宙逊卿只滑丛嫉秆缨丘民应零跪爵锹柬汉斌喊替五掣图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 11 对对于于 有有有有 向向向向 图图图图来来说说, 若若图图中中 任任任任 意意意意 一一一一 对对对对 顶顶顶顶 点点点点 v vi i和和和和v vj j(ij)(ij)均均均均有有有有从从从从v vi i到到到到 v vj j及及及及从从从从 v vj j到到到到 v vi i的的的的有有有有向向向向路路路路径径径径, 则则称称该该有向图是强连通的有向图是强连通的有向图是强
13、连通的有向图是强连通的。强连通图和非强连通图示例见图强连通图和非强连通图示例见图:国谬粹捎夺霉府型代狠丘彰人冯诗遵养勘忙婶瑟建抡伶速天敷菲碍哭民应图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 12连通分量和强连通分量连通分量和强连通分量连通分量和强连通分量连通分量和强连通分量 无无无无向向向向图图图图中中，极极大大的的连连通通子子图图为为该该图图的的连连通通分分量量。显显然然，任任何何连连通通图图的的连连通通分分量量只只有有一一个个，即即它它本本身身，而而非连通图有多个连通分量。非连通图有多个连通分量。24351672435167衔莽宝示芦殃畜猫云盆剐助芒猩垫嘲直
14、枣考岩恕景练才瘦涯防奔庞洽悍峰图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 13 有有向向图图中中的的极极极极大大大大强强强强连连连连通通通通子子子子图图图图称称为为该该有有向向图图的的强强强强连连连连通通通通分分分分量量量量。显显然然，任任何何强强连连通通图图的的强强连连通通分分量量只只有有一一个个，即即它本身，而非强连通图有多个强连通分量。它本身，而非强连通图有多个强连通分量。 下图不是强连通的下图不是强连通的, 但它有两个强连通分量但它有两个强连通分量:132321班衍昼粟拧驳惦姆秩挝糟舟囤葛田凰熊电郎丽盏巡红垫奥差骡丫檀寐硼凿图及其应用(new)图及其应用
15、(new)第第10章章 图及其应用图及其应用 14顶点的度顶点的度顶点的度顶点的度2341如：顶点如：顶点1的度为的度为3132如：顶点如：顶点2的入度为的入度为2 出度为出度为1有向图有向图有向图有向图中中, 要区别顶点的入度和出度的概念。要区别顶点的入度和出度的概念。 顶点顶点v的的入度入度入度入度 是指是指以以以以v v为终点的弧的数目为终点的弧的数目为终点的弧的数目为终点的弧的数目记为记为ID(v) 顶点顶点v的的出度出度出度出度 是指是指以以以以v v为始点的弧的数目为始点的弧的数目为始点的弧的数目为始点的弧的数目记为记为OD(v) 显然：显然：D(v)=ID(v)+OD(v) 顶点
16、的顶点的度度度度 是指是指依附于某顶点依附于某顶点依附于某顶点依附于某顶点v vi i的边数的边数的边数的边数, 通常记通常记 为为D(v)特兰污抓寄拔尿豫疤触勘厅妄堵塔筷负抉弹枝冗庙忆盈咐桑惋室邮齐萝揪图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 15 10.1 图的概念 10.2 图的存储 10.3 图的遍历 10.4 生成树和最小生成树 10.5 最短路径 10.6 有向无环图的应用第10章 图及其应用末雅串胯哇认苑播役惜蒲蛆川逃压嘻睁乃戍禄霞膀星蓬袄辨摩锡孽氦琉胀图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 16 10.2.1
17、 邻接矩阵存储法 10.2.2 邻接表表示法 10.2.3 十字链表 10.2.4 邻接多重表 10.2 图的存储之茬功捻倒沪舱睛坷电悍俐肌巴蛙皆讳辣睁揭洛悲眼脖褐堂鹊板艇炼菠承图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 17邻接矩阵：邻接矩阵：邻接矩阵：邻接矩阵：用一个二维数组（矩阵）来表示图中顶点之间的相邻关系。 设图设图G=(V, VR)有有n(n1)个顶点个顶点, 则则G的邻接矩阵是按如的邻接矩阵是按如下定义的下定义的n阶方阵阶方阵: 1 若若(vi,vj)或或VR(G) aij= 0 反之反之椎悍忙玉摩铃梭尝场盗铰迸瑞帚潜驱槐演螺拾岭裴岿选接颂茫周夫奢
18、巢嚎图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 18例例例例: : 图图G1、 G2的的邻邻接接矩矩阵阵分分别别表表示示为为A1和和A2, 矩矩阵阵的的行、行、 列号对应于图中结点的号。列号对应于图中结点的号。 0 1 1 11 0 1 01 1 0 11 0 1 00 1 10 0 10 1 02341132G1G2滤裂菜铺烬哉崖总胞睛铆霉赋伦埃撤拇根每拄侄葱慈蓄狱涩写牙植捡坐戮图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 19从无向图的邻接矩阵可以得出如下结论：从无向图的邻接矩阵可以得出如下结论：从无向图的邻接矩阵可以得出如下结
19、论：从无向图的邻接矩阵可以得出如下结论： （1）矩阵是对称的，可压缩存储（上（下）三角）矩阵是对称的，可压缩存储（上（下）三角）;（2）第）第i行或第行或第i 列中列中1的个数为顶点的个数为顶点i 的度的度;（3）矩阵中）矩阵中1的个数的一半为图中边的数目的个数的一半为图中边的数目;（4）很很容容易易判判断断顶顶点点i 和和顶顶点点j之之间间是是否否有有边边相相连连(看看矩阵中矩阵中i行行j列值是否为列值是否为1)。没梆贸戍恭象胆塔晰酿褒堵绥彪傻炎滤歇褂靛鼠庄掌婚桂肋厕研崔靛刁迹图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 20从有向图的邻接矩阵可以得出如下结论从
20、有向图的邻接矩阵可以得出如下结论从有向图的邻接矩阵可以得出如下结论从有向图的邻接矩阵可以得出如下结论: :（1） 矩阵不一定是对称的矩阵不一定是对称的;（2） 第第i 行中行中1的个数为顶点的个数为顶点i 的出度的出度;（3） 第第i列中列中1的个数为顶点的个数为顶点 i的入度的入度;（4） 矩阵中矩阵中1的个数为图中弧的数目的个数为图中弧的数目;（5） 很容易判断顶点很容易判断顶点i 和顶点和顶点j 是否有弧相连是否有弧相连.娥瞳侧色稿蠢几简华砒酣奥龚纂衫段莫浚矩酮闹炊祟韵襟陷傻摘心引遂悯图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 21 网的邻接矩阵表示：网的
21、邻接矩阵表示：网的邻接矩阵表示：网的邻接矩阵表示： 若图若图G是一个有是一个有n个顶点的网，则它的邻接矩阵是具有个顶点的网，则它的邻接矩阵是具有如下性质的如下性质的nn矩阵矩阵A： 若若或或(vi, vj) VR(G)反之反之 脏臂单垛拔彻褒蛾寇蹋窥谰爵准蔼育戊仁坎祟轩蠢粗禁币旅簧怔逛垢柴琐图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 22 5 7 4 8 5 234158475例：例：例：例：一个有向网一个有向网N及其邻接矩阵的示例。及其邻接矩阵的示例。 醛么夸看阵顾雪缝疲晃裳塘愚粪帐矽捍停超蔷倒疗吠疮氖摔谴哗刊芥腻合图及其应用(new)图及其应用(new)第第
22、10章章 图及其应用图及其应用 23 n n个顶点需要个顶点需要n*nn*n个单元存储边个单元存储边( (弧弧););空间效率为空间效率为O O(n(n2 2) )。 对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。对稀疏图而言尤其浪费空间。邻接矩阵法邻接矩阵法优点：优点：邻接矩阵法邻接矩阵法缺点：缺点： 容易实现图的操作，如：求某顶点的度、判断顶点容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。之间是否有边（弧）、找顶点的邻接点等等。勾拎蛔蔚嘘翻啊澜禄烹携澎燃自科情弃藻众眠吵液落莫桂候叫俯僳猖遣讶图及其应用(new)图及其应用
23、(new)第第10章章 图及其应用图及其应用 24邻接矩阵表示法的邻接矩阵表示法的C语言类型描述如下：语言类型描述如下： define MAX_V_N 10 / /最多顶点个数最多顶点个数最多顶点个数最多顶点个数define INFINITY 32768 / /表示极大值，表示极大值，表示极大值，表示极大值， 即即即即 typedef enumDG, DN, UDG, UDNenumDG, DN, UDG, UDN GraphKind; / /图图图图的的的的种种种种类类类类：DGDG表表表表示示示示有有有有向向向向图图图图, , DNDN表表表表示示示示有有有有向向向向网网网网, , UDG
24、UDG表表表表示无向图示无向图示无向图示无向图, UDN, UDN表示无向网表示无向网表示无向网表示无向网醇杠景淌聋久辰登牛断五茎暂渗橡掀佐祸何下谈勤仰拽镑赶氰团债啼碾韶图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 25typedef struct ArcNodestruct ArcNode AdjType adj; AdjType adj; / / AdjTypeAdjType是是是是顶顶顶顶点点点点关关关关系系系系类类类类型型型型，对对对对无无无无权权权权图图图图，用用用用1 1或或或或0 0表表表表示是否相邻；对带权图，则为权值类型示是否相邻；对带权图，则为
25、权值类型示是否相邻；对带权图，则为权值类型示是否相邻；对带权图，则为权值类型 InfoType *info;InfoType *info; / /该弧相关信息的指针该弧相关信息的指针该弧相关信息的指针该弧相关信息的指针 ArcNode; 耳刊岸单闺舷电涪芍泽杉卸扶撰唯痒取刘硼查席宏锥翰这产议煮诞肢骸化图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 26 typedef structstruct VertexData VertexData vexsMAX_V_N;vexsMAX_V_N; / /顶顶顶顶点点点点向向向向量量量量 ArcNode ArcNode arcs
26、MAX_V_NMAX_V_N;arcsMAX_V_NMAX_V_N; / /邻邻邻邻接接接接矩矩矩矩阵阵阵阵 int vexnum, arcnum;int vexnum, arcnum; / /图的顶点数和弧数图的顶点数和弧数图的顶点数和弧数图的顶点数和弧数 GraphKind kind;GraphKind kind; / /图的种类标志图的种类标志图的种类标志图的种类标志 AdjMatrix; /(Adjacency Matrix Graph)/(Adjacency Matrix Graph) 竹蝇冀秒寞澄堡郭呻法棒拆仓闻御年荧熏经榆负龄颂雪寓滤殉掸啸叉农灾图及其应用(new)图及其应用(n
27、ew)第第10章章 图及其应用图及其应用 27int LocateVertex(AdjMatrix * G, VertexData v)/求顶点位置函数求顶点位置函数 int j = -1, k; for(k=0; kvexnum; k+) if(G-vexsk = = v) j = k; break; return(j); 山洒脯茄杂义晾敦锑民莽蔗珠季伯超倔衬吟雨龙偶角韧游膀圈痴绝稚谢麻图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 28int CreateDN(AdjMatrix *G) /创建有向网创建有向网 int i, j, k, weight; Vert
28、exData v1, v2; scanf(%d, %d, &G-arcnum, &G-vexnum); / /输入图的顶点数和弧数输入图的顶点数和弧数输入图的顶点数和弧数输入图的顶点数和弧数 for(i=0; ivexnum; i+) / /初始化邻接矩阵初始化邻接矩阵初始化邻接矩阵初始化邻接矩阵 for(j=0; jvexnum; j+) G-arcsij.adj = INFINITY; for(i=0; ivexnum; i+) scanf(%c, &G-vexsi); / /输入图的顶点值输入图的顶点值输入图的顶点值输入图的顶点值伶菊龟挽香烈呸菊雕雷刀慕弦傍炙桩蔫沿宝斧未初戎便瞧机因傻抚
29、武戊牙图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 29 for(k=0; karcnum; k+) scanf(%c, %c, %d, &v1, &v2, &weight); / /输入一条弧的两个顶点及权值输入一条弧的两个顶点及权值输入一条弧的两个顶点及权值输入一条弧的两个顶点及权值 i=LocateVex(G, v1); / /求顶点位置函数求顶点位置函数求顶点位置函数求顶点位置函数 j=LocateVex(G, v2); G-arcsij.adj = weight; / /建立弧建立弧建立弧建立弧 return(Ok); 突拌需末删痒帝硕媒街叮卉窜军谎靳剧
30、独藕灶映荚卞操吭柑鹿垛芭拾吭蝎图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 30 10.2.1 邻接矩阵存储法 10.2.2 邻接表表示法 10.2.3 十字链表 10.2.4 邻接多重表10.2 图的存储早峡冻次渍灰父滇疹腐整咋锑馏矛萌梢供彦皑碌竣胀南枣欢养曲袖韧畏膀图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 31 邻接表（邻接表（Adjacency List）表示法是图的一种链式存）表示法是图的一种链式存储结构。它包括两个部分储结构。它包括两个部分, 一部分是一部分是链表链表链表链表, 另一部分是另一部分是向量向量向量向量。 在
31、在链表部分中共有链表部分中共有链表部分中共有链表部分中共有n n个链表个链表个链表个链表(n为顶点数为顶点数), 用来存放边用来存放边的信息。的信息。 将将每个单链表的表头结点顺序存储在一个向量中每个单链表的表头结点顺序存储在一个向量中每个单链表的表头结点顺序存储在一个向量中每个单链表的表头结点顺序存储在一个向量中。2341煮牌亮硕恳它替悄崎擎惑毛峭蒋孺晾看瓢粪钉引缠瞥赘泻熔支歇可悬耙绒图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 32 这这样样，一一个个n个个顶顶点点的的图图的的邻邻接接表表表表示示由由表表表表头头头头结结结结点点点点表表表表与与边表边表边表边表
32、两部分构成：两部分构成： (1) (1) 表表表表头头头头结结结结点点点点表表表表：由由所所有有表表头头结结点点以以顺顺序序结结构构（向向量量）的形式存储的形式存储.。 表表头头结结点点的的结结构构如如图图所所示示，由由两两部部分分构构成成：数数数数据据据据域域域域 （ vexdatavexdata） 用用 于于 存存 储储 顶顶 点点 的的 名名 (值值 )； 链链链链 域域域域（firstarcfirstarc）用用于于指指向向链链表表中中第第一一个个顶顶点点（即即与与顶顶点点vi邻邻接的第一个邻接点）。接的第一个邻接点）。 vexdatavexdatafirstarcfirstarc徐跪
33、犊屠谊辨升涵避猜宦博囤边佃匝畴升诀果买学褂选副羹整资委讨沪藩图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 33(2) (2) 边表：边表：边表：边表：由邻接点链式存储的单链表。由邻接点链式存储的单链表。 单链表中每个结点由三个域组成单链表中每个结点由三个域组成: 邻接点域邻接点域邻接点域邻接点域(adjvex)(adjvex)指示与顶点指示与顶点vi 邻接的点在图中的位置；邻接的点在图中的位置；链域链域链域链域(nextarc)(nextarc) 指向顶点指向顶点vi 的下一个邻接点；的下一个邻接点；数据域数据域数据域数据域(info)(info) 存储和边存储和
34、边(或弧或弧)相关的信息相关的信息,如权值等。如权值等。adjvexadjvexnextarcnextarcinfoinfo乙曙炯苇开允宁眼韦蔓气乾邪勾膏伺舒搞印渗括阮痹砧绩懈榷气找背舱糟图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 34例：例：2341陈切度肤扔揖姓排莽搅淀烤客舞也崩救训任磁炽叭秆伙由鸣泛幕赘瘁缮鄙图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 355423415囊张涂稀助荷喧大幅疑泰丢栽沽厩洼首葬砌醋赏址专茫陡拟期倘撅貌呈烧图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 36从无向图的邻接
35、表可以得到如下结论：从无向图的邻接表可以得到如下结论：从无向图的邻接表可以得到如下结论：从无向图的邻接表可以得到如下结论： （1）第）第i 个链表中结点数目为顶点个链表中结点数目为顶点i的度；的度；（2）所有链表中结点数目的一半为图中边数；）所有链表中结点数目的一半为图中边数；（3）占用的存储单元数目为）占用的存储单元数目为n+2e (e为边数为边数)。烈侮檄丸垦仆奸掣竿蝇由紊坊温质羽饿恳媳装渐雪栓缺玛自孰选屠切九消图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 37从有向图的邻接表可以得到如下结论从有向图的邻接表可以得到如下结论从有向图的邻接表可以得到如下结论从有
36、向图的邻接表可以得到如下结论: :（1）第）第i 个链表中结点数目为顶点个链表中结点数目为顶点i的出度；的出度；（2）所有链表中结点数目为图中弧数；）所有链表中结点数目为图中弧数；（3）占用的存储单元数目为）占用的存储单元数目为n+e 。 从有向图的邻接表可知，不能求出顶点的入度。从有向图的邻接表可知，不能求出顶点的入度。若要求第若要求第i个顶点的个顶点的入度入度入度入度，必须，必须遍历整个邻接表遍历整个邻接表遍历整个邻接表遍历整个邻接表，在所，在所有边链表中查找有边链表中查找邻接点域的值为邻接点域的值为邻接点域的值为邻接点域的值为i i的结点并计数的结点并计数的结点并计数的结点并计数求和。求
37、和。由此可见，由此可见， 对于用邻接表方式存储的有向图，求顶点对于用邻接表方式存储的有向图，求顶点的入度并不方便，的入度并不方便， 它需要通过扫描整个邻接表才能得它需要通过扫描整个邻接表才能得到结果。到结果。 栖训壹拟旧棱朱是断苗叛壹都羹惕冷车圣般搔开怀隙担烫斜兼睛嫌敝逞仲图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 38 解解解解决决决决的的的的方方方方法法法法：逆逆逆逆邻邻邻邻接接接接表表表表法法，对对每每一一顶顶点点vi再再建建立立一一个个逆逆邻邻接接表表，即即对对每每个个顶顶点点vi建建立立一一个个所所有有以以顶顶点点vi为为弧弧头头的弧的表，如图所示：的
38、弧的表，如图所示： 2341摄记驹楼缅巷轻为寿硬两访撑鲜峭喧呼咙未硝践躇剥困窍谚觅牧涅烬希拢图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 39邻接表的邻接表的邻接表的邻接表的缺点：缺点：缺点：缺点：邻接表的邻接表的邻接表的邻接表的优点：优点：优点：优点：空间效率高；空间效率高；容易寻找顶点的邻接点；容易寻找顶点的邻接点； 判断两顶点间是否有边或弧，需搜索两结点判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。对应的单链表，没有邻接矩阵方便。燥氢龟剿玄倚阜京帚药丧罗惊溜禹椿忙北厘鸯杜窒廷祷欠哀赌框绝辑较驱图及其应用(new)图及其应用(new)第
39、第10章章 图及其应用图及其应用 40define MAX_V_N 10 / /最多顶点个数最多顶点个数最多顶点个数最多顶点个数typedef enumenum DG, DN, UDG, UDN DG, DN, UDG, UDN GraphKind; / /图的种类图的种类图的种类图的种类typedef struct ArcNodestruct ArcNode int adjvex; int adjvex; / /该弧指向顶点的位该弧指向顶点的位该弧指向顶点的位该弧指向顶点的位置置置置 struct ArcNode *nextarc;struct ArcNode *nextarc; / /指向
40、下一条弧的指针指向下一条弧的指针指向下一条弧的指针指向下一条弧的指针 InfoType *info;InfoType *info; / /该弧相关信息的指该弧相关信息的指该弧相关信息的指该弧相关信息的指针针针针 ArcNode; /边表中结点的类型边表中结点的类型邻接表存储结构的形式化说明如下：邻接表存储结构的形式化说明如下： 杠蔚比脊鸦隙戴错泊帆鹰钵椅兼瘤么讶泵胶宙崭壹严继瓦凋阂拾柒局粗养图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 41typedef struct VertexNodestruct VertexNode VertexData verdata;
41、VertexData verdata; / /顶点数据顶点数据顶点数据顶点数据 ArcNode *firstarc;ArcNode *firstarc; / /指向下一个邻接点指向下一个邻接点指向下一个邻接点指向下一个邻接点 VertexNode; /表头结点表中结点的类型表头结点表中结点的类型typedef structstruct VertexNode vertexMAX_V_N; VertexNode vertexMAX_V_N; int vexnum, arcnum; int vexnum, arcnum; / /图的顶点数和弧数图的顶点数和弧数图的顶点数和弧数图的顶点数和弧数 Gra
42、phKind kind;GraphKind kind; / /图的种类标志图的种类标志图的种类标志图的种类标志 AdjList; /基于邻接表的图基于邻接表的图(Adjacency List Graph) 现库渔秒故遁逢姑佛拌羡战悟休郧饶励酶迟掐防身劲蛛慢亢僻当醛闸震宇图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 42讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？讨论：邻接表与邻接矩阵有什么异同之处？1. 1. 1. 1. 联系：联系：联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每
43、个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。2. 2. 2. 2. 区别：区别：区别：区别： 对于任一确定的无向图，邻接矩阵是唯一的（行列号对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。点编号无关）。 邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复杂而邻接表的空间复杂度为度为O(n+e)O(n+e)。飞匹翅今萧腾脊紧萧皆典璃惋擦畔蝉臼常端罢钠呈馅先槐枫鸦煌滋脊绳技图及其应用(new)图
44、及其应用(new)第第10章章 图及其应用图及其应用 43 10.2.1 邻接矩阵存储法 10.2.2 邻接表表示法 10.2.3 十字链表 10.2.4 邻接多重表 10.2 图的存储挖垦书蜒梆裴与玖峦蚜嗡撰蓄贝枝惊极螺儡撤旁雄懂流循缨罢蘸苫田哇弃图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 44 十字链表是有向图的另一种链式存储结构。在十字十字链表是有向图的另一种链式存储结构。在十字链表中，链表中，对应于有向图中每一条弧有一个结点（对应于有向图中每一条弧有一个结点（对应于有向图中每一条弧有一个结点（对应于有向图中每一条弧有一个结点（弧结弧结弧结弧结点点点点）:
45、 :tailvextailvexheadvexheadvexhlinkhlinktlinktlinkinfoinfo弧尾顶点在弧尾顶点在图中的位置图中的位置弧头顶点在弧头顶点在图中的位置图中的位置指向与此弧弧头指向与此弧弧头相同的下一条弧相同的下一条弧指向与此弧弧尾指向与此弧弧尾相同的下一条弧相同的下一条弧指向该弧的指向该弧的相关信息相关信息嘘构积褐虎撬赚斟英拂傲辛暇伞收怖蚂自香耐添籽免废兜戴竖型拄命竞凿图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 45对应于每个顶点也有一个结点（对应于每个顶点也有一个结点（顶点结点顶点结点顶点结点顶点结点）：）：指向以该顶点作为
46、弧头指向以该顶点作为弧头的第一个弧顶点的第一个弧顶点存储与顶点有关的信息存储与顶点有关的信息, ,如顶点的名字等如顶点的名字等指向以该顶点作为弧指向以该顶点作为弧尾的第一个弧顶点尾的第一个弧顶点datafirstinfirstout址妆得詹匿复竞雪诞咽镰诵紫弱褂此雍歉獭倦圾砾拓瘁迸汛劳活莆汾韦铸图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 46123412341213 34 234141 氰缉速楷夕断体吻厉茵琐比族说焰狈浊峻唬笆揍撩茧达完革藩会王戴员互图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 47图的十字链表结构形式化定义如下：图
47、的十字链表结构形式化定义如下：图的十字链表结构形式化定义如下：图的十字链表结构形式化定义如下：define MAX_V_N 10 /*/*最多顶点个数最多顶点个数最多顶点个数最多顶点个数*/*/typedef enumDG, DN, UDG, UDNenumDG, DN, UDG, UDN GraphKind; /*/*图的种类图的种类图的种类图的种类*/*/ typedef struct ArcNodestruct ArcNode int tailvex, headvex; int tailvex, headvex; struct ArcNode *hlink, *tlink; struct
48、 ArcNode *hlink, *tlink; InfoType *info ; InfoType *info ; ArcNode; /*弧结点的类型弧结点的类型*/兵募块磁匀尹眠床署氓懦搀掂号渊捻聊脚喉蔓薯澡壕甫削酣朔念逸点逆蔑图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 48typedef struct VertexNodestruct VertexNode VertexData data; VertexData data; /*/*顶点信息顶点信息顶点信息顶点信息*/*/ ArcNode *firstin, *firstout; ArcNode *firs
49、tin, *firstout; VertexNode; /*顶点结点的类型顶点结点的类型*/typedef structstruct VertexNode vertexMAX_V_N; VertexNode vertexMAX_V_N; int vexnum, arcnum; int vexnum, arcnum; /*/*图的顶点数和弧数图的顶点数和弧数图的顶点数和弧数图的顶点数和弧数*/*/ GraphKind kind;GraphKind kind; /*/*图的种类图的种类图的种类图的种类*/*/ OrthList; /*图的十字链表表示法图的十字链表表示法(Orthogonal Li
50、st)*/ 预弄戒责恳夸唤阮麓驱咽挡有能疏瞒建掖溪艇扒税央胖熬辜迪八粤诡富粉图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 49 10.2.1 邻接矩阵存储法 10.2.2 邻接表表示法 10.2.3 十字链表 10.2.4 邻接多重表 10.2 图的存储檬鹃戒诊控卸陕诌楷卷督崇恫艾愿啮醉典芜乾乏松豌珊鸡邻虹媳拒钳添窄图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 50 邻接多重表邻接多重表邻接多重表邻接多重表是无向图的另一种链式存储结构。在是无向图的另一种链式存储结构。在邻接多重表中，邻接多重表中，每一条边用一个结点表示，该结点有每一条
51、边用一个结点表示，该结点有每一条边用一个结点表示，该结点有每一条边用一个结点表示，该结点有六个域：六个域：六个域：六个域：markivexilinkjvexjlinkinfo标记该条边是标记该条边是否被搜索过否被搜索过指向下一依附指向下一依附于顶点于顶点i的边的边该边的一个该边的一个顶点在图中顶点在图中的位置序号的位置序号该边的另一个该边的另一个顶点在图中顶点在图中的位置序号的位置序号指向下一指向下一条依附于条依附于顶点顶点j的边的边指向该弧的指向该弧的相关信息相关信息餐砍燎泵乱灼忘僵助嚷陌橡财际姻义龚趁缆促候汹呢贴碍腋暑初擞触蹿谜图及其应用(new)图及其应用(new)第第10章章 图及其应
52、用图及其应用 51 每一个顶点也用一个结点表示，该结点有两个域：每一个顶点也用一个结点表示，该结点有两个域：datafirstedge存储与顶点有存储与顶点有关的信息，如关的信息，如顶点的名字顶点的名字指向第一条依附指向第一条依附于该顶点的边于该顶点的边矢粪狱粟选侈桨嘉寺伶槽财妆黍恭眠竟趾郡玻赂肋褪朴杠捐惰模鸽酸柬跨图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 5235143234521212345123454523415溯砸箍刊舷病哄单锤貌荚茅赡劳胆鼎涝诧辖庆熙窟亭牟萍舵矮钳额择憎颁图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 53
53、邻接多重表的结构类型说明如下：邻接多重表的结构类型说明如下： typedef struct struct VertexData data; VertexData data; EdgeNode *firstedge; EdgeNode *firstedge; VertexNode; /*顶点结点的类型顶点结点的类型*/橱洪付愉鸥全绒疤沛旭恤识颤井彩琅翟筋麦博跺病滇配犬赛哀汲海谭溢湿图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 54typedef struct EdgeNode struct EdgeNode int mark, ivex, jvex; int mar
54、k, ivex, jvex; struct EdgeNode *ilink, *jlink; struct EdgeNode *ilink, *jlink; InfoType *info ; InfoType *info ; EdgeNode; /*边结点的类型边结点的类型*/typedef structstruct VertexNode vertexMAX_V_N; VertexNode vertexMAX_V_N; int vexnum, arcnum; int vexnum, arcnum; /*/*图的顶点数和弧数图的顶点数和弧数图的顶点数和弧数图的顶点数和弧数*/*/ GraphKi
55、nd kind; /*GraphKind kind; /*图的种类图的种类图的种类图的种类*/*/ AdjMultiList; /*基于图的邻接多重表表示法基于图的邻接多重表表示法(Adjacency Multi-list)*/那花乏侈磺混放视森守替泌矽操侥梯舆独锻蒋陪妈勉秧弹脖蛾标葬焦滋荐图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 55分析分析分析分析: : 在图的链接存储在图的链接存储(邻接表、逆邻接表、十字链表邻接表、逆邻接表、十字链表和邻接多重表和邻接多重表)中，表头向量需要占用中，表头向量需要占用n个存储单元，个存储单元，所有边结点需要占用所有边结点需
56、要占用2e或或e存储单元，所以最多需要存储单元，所以最多需要（n+2e）个存储单元，稀疏图采用这种存储方式可）个存储单元，稀疏图采用这种存储方式可节省存储空间。节省存储空间。迂鞍副史姚辗滁悦职管笑椽石形楞逻宣犬做财崎藩炉掀苞栋葫讽瞒摩境驯图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 56 10.1 图的概念 10.2 图的存储 10.3 图的遍历 10.4 生成树和最小生成树 10.5 有向无环图的应用 10.6 最短路径第10章 图及其应用臆脾唾亏缎缓娩碘朋南福硫笛贞嗜养驹安岩橙肢洽蜗藐巫恼绞猴封拥寿烘图及其应用(new)图及其应用(new)第第10章章 图及其
57、应用图及其应用 57图图图图的的的的遍遍遍遍历历历历：沿沿着着某某条条搜搜索索路路径径对对图图中中所所有有顶顶点点各各作一次访问。作一次访问。 图图的的遍遍历历比比起起树树的的遍遍历历要要复复杂杂得得多多。图图中中顶顶点点关关系系是是多多对对多多的的关关系系，图图可可能能是是非非连连通通图图，图图中中还还可可能能有有回回路路存存在在， 因因此此在在访访问问了了某某个个顶顶点点后后，可可能能沿沿着着某某条路径搜索后又回到该顶点上。条路径搜索后又回到该顶点上。 为为为为了了了了保保保保证证证证图图图图中中中中的的的的各各各各顶顶顶顶点点点点在在在在遍遍遍遍历历历历过过过过程程程程中中中中访访访访问
58、问问问且且且且仅仅仅仅访访访访问一次，需要为每个顶点设一个访问标志问一次，需要为每个顶点设一个访问标志问一次，需要为每个顶点设一个访问标志问一次，需要为每个顶点设一个访问标志。 浸蠕始红枢廊额举业择匀奔主他夸玉舆兼岭殴绷忱贪卓陆走鞍削站午燃砾图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 58 为为此此 我我们们设设置置一一个个访访访访问问问问标标标标志志志志数数数数组组组组visitednvisitedn，用用于于标标示示图图中中每每个个顶顶点点是是否否被被访访问问过过，它它它它的的的的初初初初始始始始值值值值为为为为0(“0(“假假假假”)”)，表表表表示示示示
59、顶顶顶顶点点点点均均均均未未未未被被被被访访访访问问问问；一一一一旦旦旦旦访访访访问问问问过过过过顶顶顶顶点点点点vivi，则则置置访访问问标标志志数数组组中中的的visitedivisitedi为为为为1(“1(“真真真真”)”)，以以表表示示该该顶顶点点已访问。已访问。 根据搜索路径的不同，图的遍历又分：根据搜索路径的不同，图的遍历又分： 深度优先搜索遍历深度优先搜索遍历深度优先搜索遍历深度优先搜索遍历 广度优先搜索遍历广度优先搜索遍历广度优先搜索遍历广度优先搜索遍历 险畔蜜定宿凶戒请绽茅捅忆忧犀标舒窄女上佯调傲降嵌帖泻暇岗隧醛靴宾图及其应用(new)图及其应用(new)第第10章章 图及
60、其应用图及其应用 5910.3.1 深度优先搜索遍历 10.3.2 广度优先搜索遍历 10.3 图的遍历情逛思宜葱淬蚤躲鳞割井耪友缕叫尧啃悄澄洞们釉硼橡条塞非股贯询淹促图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 60 深深深深度度度度优优优优先先先先搜搜搜搜索索索索（Depth-First Search）是是指指按按照照深深度度方方向向搜搜索索，它它类类似似于于树树的的先先根根遍遍历历，是是树树的的先先根根遍遍历的推广。历的推广。 特点：特点：特点：特点：尽可能先对纵深方向进行搜索。尽可能先对纵深方向进行搜索。算法描述：算法描述：算法描述：算法描述： 从某个顶点
61、从某个顶点v0出发，进行出发，进行dfs的算法描述如下：的算法描述如下： (1) (1) 访问访问访问访问v v0 0 。 (2) (2) 依次从依次从依次从依次从v0v0的未被访问的邻接点出发作深度遍历的未被访问的邻接点出发作深度遍历的未被访问的邻接点出发作深度遍历的未被访问的邻接点出发作深度遍历皑纱妒渡棉朱缎窟阎咖帜折曾另隅蔼要焦敲不夏袭厩敛龙汗牲折耽桓桌奇图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 61BAGDCFHEI 下图给出了一个深度优先搜索的过程图示，其中下图给出了一个深度优先搜索的过程图示，其中实实实实箭头代表访问方向，虚箭头代表回溯方向箭头代表
62、访问方向，虚箭头代表回溯方向箭头代表访问方向，虚箭头代表回溯方向箭头代表访问方向，虚箭头代表回溯方向，箭头旁边的，箭头旁边的数字代表搜索顺序，数字代表搜索顺序， A A为起始顶点为起始顶点为起始顶点为起始顶点。 神炸东程默蛔请盒霉亏描迈典抵岔皇肖难妹笨异我嗣绷坞捂踪后坤允紫库图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 62 若若若若图图图图是是是是连连连连通通通通的的的的或或或或强强强强连连连连通通通通的的的的，则则从从图图中中某某一一个个顶顶点点出出发发可可以以访访问问到到图图中中所所有有顶顶点点，否否则则只只能能访访问问到到一一部部分顶点。分顶点。 另外，从
63、刚才写出的遍历结果可以看出，从某一另外，从刚才写出的遍历结果可以看出，从某一个顶点出发的遍历结果是不唯一的。但是个顶点出发的遍历结果是不唯一的。但是,若我们给若我们给定图的存贮结构定图的存贮结构,则从某一顶点出发的遍历结果应是则从某一顶点出发的遍历结果应是唯一的。唯一的。 分析与总结：分析与总结：分析与总结：分析与总结：枪连鹃尽仇菠尧裳咳滤沤荔想帅垄蹦闸牟剔狈钱睬耶炙湖塌棠苫艺秸臣浓图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 63分析连通图的深度遍历算法的实现分析连通图的深度遍历算法的实现分析连通图的深度遍历算法的实现分析连通图的深度遍历算法的实现: :(1)
64、为为防防止止重重复复访访问问顶顶点点，需需为为为为每每每每个个个个顶顶顶顶点点点点设设设设置置置置一一一一个个个个访访访访问问问问标标标标志志志志 visitedivisitedi ，其其值值为为 0 时时，表表示示顶顶点点 i 未未被被访访问问过；值为过；值为 1 时，表示顶点时，表示顶点 i 已被访问过。已被访问过。(2) 算算法法中中需需依依依依次次次次找找找找v0v0的的的的各各各各邻邻邻邻接接接接点点点点，可可根根据据不不同同的的存存储储结结构构具具体体实实现现。这这里里为为简简化化描描述述，给给出出两两个个自自定定义义函数：函数： 扬握绘鲍攻册傍戈岁泻痹虏宪词霖搅捆笋韧并无镍侵彝旬
65、痛态杉局限韶瘦图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 64 FirstAdjVertex(g, v0)FirstAdjVertex(g, v0) ：返回图：返回图G中顶点中顶点v0的第一个邻的第一个邻接点的编号，若不存在，返回接点的编号，若不存在，返回 0 。 NextAdjVertex(g, v0, w)NextAdjVertex(g, v0, w)：返回图：返回图G中顶点中顶点 v0的邻接的邻接点中，处于点中，处于 w 之后的那个邻接点的编号；若不存在，则之后的那个邻接点的编号；若不存在，则返回返回 0 。 啼机沽返屉钠庇鹊诬冉循苫琅盲饲坎醉蛤击雇钟明雀
66、侯终誉置凶场硼耶木图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 65访问 v0置访问标志visitedv0=1w = FirstAdjVertex(g,v0) w = = 0 w 已被访问过dfs(g ,w) w= NextAdjVertex(g , v0, w)N NN NY YY Y结束结束结束结束揽辣肩诊凯浇摄石颠钞哪港草匣颗软氨慕穴拇圈秋跋阅侥坛材悉措瘁洲立图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 66 算法算法算法算法1 1：深度遍历：深度遍历：深度遍历：深度遍历v0v0所在的连通子图所在的连通子图所在的连通子图所在的连
67、通子图void DFS（Graph g, int v0） visit（v0）； visitedv0 =True； / /访问顶点访问顶点v0v0， 并置访问标志数组相应分量值并置访问标志数组相应分量值 w=FirstAdjVertex(g, v0); while ( w! = -1) / /邻接点存在邻接点存在 if(! visited w ) DFS(g, w); / /递归调用递归调用DFSDFS w=NextAdjVertex(g, v0, w); / /找下一个邻接点找下一个邻接点 /DepthFirstSearch囊煌该鸡扼乃夏日糖铡是诬咎伐诸裹茸枷甘饵策辈伊哄氛种淌将无寸逗忱图及其
68、应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 67非连通图的深度优先搜索：非连通图的深度优先搜索：非连通图的深度优先搜索：非连通图的深度优先搜索： 若若图图图图是是是是非非非非连连连连通通通通的的的的或或或或非非非非强强强强连连连连通通通通图图图图，则则从从图图中中某某一一个个顶顶点点出出发发。不不不不能能能能用用用用深深深深度度度度优优优优先先先先搜搜搜搜索索索索访访访访问问问问到到到到图图图图中中中中所所所所有有有有顶顶顶顶点点点点，而而只只能能访访问问到到一一个个连连通通子子图图（既既连连通通分分量量）或只能访问到一个强连通子图（既强连通分量）。或只能访问到一个强
69、连通子图（既强连通分量）。 这这时时，可可可可以以以以在在在在每每每每个个个个连连连连通通通通分分分分量量量量或或或或每每每每个个个个强强强强连连连连通通通通分分分分量量量量中中中中都都都都选选选选一一一一个个个个顶顶顶顶点点点点，进进进进行行行行深深深深度度度度优优优优先先先先搜搜搜搜索索索索遍遍遍遍历历历历，最最后后将将每每个个连连通通分分量量或或每每个个强强连连通通分分量量的的遍遍历历结结果果合合起起来来，则得到整个非连通图的遍历结果。则得到整个非连通图的遍历结果。锈答盟襄慷移埂拜讯型建收慷蒋纪导叁潜鲍枕幅窍亩拆柒恬莽湾痹鹿窜栗图及其应用(new)图及其应用(new)第第10章章 图及其
70、应用图及其应用 68 非非连连通通图图的的遍遍历历算算法法实实现现与与连连通通图图的的只只有有一一点点不不同同，即即对对对对所所所所有有有有顶顶顶顶点点点点进进进进行行行行循循循循环环环环，反反复复调调用用连连通通图图的的深度优先搜索遍历算法即可。具体实现如下：深度优先搜索遍历算法即可。具体实现如下： for(int i=1;i=n;i+) if(!visitedi) dfs(i) ; 般如帝浪沂救罐涅侗还辗缆屹和师烛滇珐饶萤裁捡均鞋暴栗逛书还栽均响图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 69 下图是一个非连通图，按照它的邻接表进行深下图是一个非连通图，按照
71、它的邻接表进行深度优先搜索遍历，三次调用度优先搜索遍历，三次调用DFS过程得到的访问顶过程得到的访问顶点序列为：点序列为： 1， 2， 4， 3， 9 5， 6， 78， 10 匙戏李孺箕黄陌卑废融位弦候滴梳苏泥励另铃除切狭贵幕驰表奠虾籽爽迟图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 70算法算法算法算法2 2：深度优先搜索图：深度优先搜索图：深度优先搜索图：深度优先搜索图g gint visitedMAX_V_N; / /访问标志数组访问标志数组访问标志数组访问标志数组void TraverseGraph (Graph g)/ /对图对图对图对图g g进行深度
72、优先搜索，进行深度优先搜索，进行深度优先搜索，进行深度优先搜索，Graph Graph 表示图的一种存储结构，表示图的一种存储结构，表示图的一种存储结构，表示图的一种存储结构， 如如如如数组表示法或邻接表等数组表示法或邻接表等数组表示法或邻接表等数组表示法或邻接表等*/*/ for (vi=0; vig.vexnum; vi+) visitedvi= 0 ; / /访问标志数组初始化访问标志数组初始化访问标志数组初始化访问标志数组初始化 for( vi=0; vig.vexnum; vi+) / /调用深度遍历连通子图的操作调用深度遍历连通子图的操作调用深度遍历连通子图的操作调用深度遍历连通子
73、图的操作 / /若图若图若图若图g g是连通图，是连通图，是连通图，是连通图， 则此循环调用函数只执行一次则此循环调用函数只执行一次则此循环调用函数只执行一次则此循环调用函数只执行一次 if (！Visitedvi ) DFS(g， vi)； / TraverseGraph 稍殉搏胶裹铡局危柑移疫喊钩陶饺想柒趴摩狮糕煎牧统莹陪棱谬秽烛侩疹图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 71例例例例1 1： 用邻接矩阵方式实现深度优先搜索用邻接矩阵方式实现深度优先搜索用邻接矩阵方式实现深度优先搜索用邻接矩阵方式实现深度优先搜索 void DFS(AdjMatrix g
74、, int v0) / / 图图图图g g 为邻接矩阵类型为邻接矩阵类型为邻接矩阵类型为邻接矩阵类型AdjMatrix AdjMatrix visit(v0); visitedv0=True; for ( vj=0; vjadjvex) DFS（g，p-adjvex）；）； p=p-nextarc ； /DepthFirstSearch抽鲤谆啄痉涛剁旷约啸宽吉潘嚷揉梆决沛噪武猖捏胀浴吩片誉然陆家塑相图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 73 10.3.1 深度优先搜索遍历 10.3.2 广度优先搜索遍历10.3 图的遍历事扎贴选烯奴辽耻卑皑约萨话桩鼠蚊茵厩
75、且差拖畏援块欠肺潜忻锡收肘决图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 74 广度优先搜索广度优先搜索广度优先搜索广度优先搜索（Breadth-First Search）是指照广度）是指照广度方向搜索，它类似于树的层次遍历，是树的按层次遍方向搜索，它类似于树的层次遍历，是树的按层次遍历的推广。历的推广。广度优先搜索的广度优先搜索的基本思想基本思想基本思想基本思想是：是： （1） 从图中某个顶点从图中某个顶点v0出发，出发，首先访问首先访问首先访问首先访问v0v0。 （2） 依次访问依次访问依次访问依次访问v0v0的各个未被访问的邻接点。的各个未被访问的邻接点。的
76、各个未被访问的邻接点。的各个未被访问的邻接点。（3 3） 分分分分别别别别从从从从这这这这些些些些邻邻邻邻接接接接点点点点（端端端端结结结结点点点点）出出出出发发发发，依依依依次次次次访访访访问问问问它它它它们的各个未被访问的邻接点（新的端结点）。们的各个未被访问的邻接点（新的端结点）。们的各个未被访问的邻接点（新的端结点）。们的各个未被访问的邻接点（新的端结点）。跪垂杠赚农制蝗定刨乏歹致脊黑梅笔凤扫睫杏粕请贝驻刀砖骆瓶澡柱久苫图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 75BAGDCFHEIB BE ED DC CGG惨匪熄腕陷冕及僵憾鹿郭咨嚎蹲笋冻辖拖坝骇毛
77、柬后辨硫水幽鲍沛匪辕辐图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 76分析该算法的实现：分析该算法的实现：分析该算法的实现：分析该算法的实现：1 1、需需设置访问标志数组设置访问标志数组设置访问标志数组设置访问标志数组，记录已被访问过的顶点。，记录已被访问过的顶点。2 2、广度优先遍历中，访问过一个顶点后，下一个需要广度优先遍历中，访问过一个顶点后，下一个需要访问的顶点可能是任何一个已访问过的顶点的邻接访问的顶点可能是任何一个已访问过的顶点的邻接点；因此，点；因此，为寻找下一个访问顶点，需设置一个结为寻找下一个访问顶点，需设置一个结为寻找下一个访问顶点，需设置一
78、个结为寻找下一个访问顶点，需设置一个结构构构构来来保存已访问过的顶点保存已访问过的顶点保存已访问过的顶点保存已访问过的顶点。 该该结构结构结构结构应该是应该是“队列队列队列队列”：?录誉里冲制苇杀概簧俄筏记痕趾卷独彰禁祝钾销废撒妹烹锻懊蜕滋挽禹刊图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 77这样，这样，与该队列相关的操作如下：与该队列相关的操作如下：与该队列相关的操作如下：与该队列相关的操作如下：(1)(1) 开始时，将其置空；开始时，将其置空；(2)(2) 在每访问一个顶点时，将其入队；在每访问一个顶点时，将其入队；(3)(3) 在访问完一个顶点的所有后继后
79、，将其出队；在访问完一个顶点的所有后继后，将其出队；(4)(4) 若队列为空，说明每一个访问过的顶点的所有若队列为空，说明每一个访问过的顶点的所有后继均已访问完毕，遍历结束。后继均已访问完毕，遍历结束。股负迅拦凑倍翼新地驼舍秸撒窒佳厅疲罕檀呕旷臼窖潜嗣始愁脑侈述祸重图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 78访问v0; Visitedv0=1; v0入队;队空 v =队头元素; w = FirstAdjVertex(g,v)访问w; Visitedw=1; w入队w = =0 w 已访问过 w= NextAdjVertex(g , v, w)NNNYYY结束
80、结束咬曙栖戍彼舵锦釜诫轩仪隅你播栖巴骤呛溢圈蹄管疏复猎俏储褪拂捡期咳图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 79广度优先搜索连通子图的算法如下：广度优先搜索连通子图的算法如下：广度优先搜索连通子图的算法如下：广度优先搜索连通子图的算法如下： void BFS(Graph g, int v0) / /广度优先搜索图广度优先搜索图广度优先搜索图广度优先搜索图g g中中中中v0v0所在的连通子图所在的连通子图所在的连通子图所在的连通子图 visit(v0); visitedv0=True; setnull(Q); / /初始化空队初始化空队初始化空队初始化空队 e
81、nt_queue(Q, v0)； / v0/ v0进队进队进队进队 while ( ! empty(Q) v = out_queue(Q); / /队头元素出队队头元素出队队头元素出队队头元素出队 w=FirstAdj(g, v); / /求求求求v v的第一个邻接点的第一个邻接点的第一个邻接点的第一个邻接点菱现贱鹤剁汞陡宠抿取惭均杯躇灵锚碱符洲游箕剂献击性锯酌诀拣疟揖灯图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 80 while (w! = -1 ) if (!visited(w) visit(w); visitedw=True; ent_queue(Q, w
82、); w=NextAdj(g, v, w); / /求求求求v v相对于相对于相对于相对于w w的下一个邻接点的下一个邻接点的下一个邻接点的下一个邻接点 寒牙箔巷篆苔福端野呆漓带鹿涩淬三仰耻旺裔斡田司碳栓结饭咨滨异绵毯图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 81 分分析析上上述述算算法法，图图图图中中中中每每每每个个个个顶顶顶顶点点点点至至至至多多多多入入入入队队队队一一一一次次次次，因因因因此此此此外循环次数为外循环次数为外循环次数为外循环次数为n n。 当当当当图图图图g g采采采采用用用用邻邻邻邻接接接接表表表表方方方方式式式式存存存存储储储储，则则当
83、当结结点点v出出队队后后，内内内内循循循循环环环环次次次次数数数数等等等等于于于于结结结结点点点点v v的的的的度度度度。由由于于访访问问所所有有顶顶点点的的邻邻接接点点的的总总的的时时间间复复杂杂度度为为O(d0+d1+d2+dn-1)=O(e)， 因因此此图图采采用用邻邻接接表表方方式式存存储储，广广广广度度度度优优优优先先先先搜搜搜搜索索索索算算算算法法法法的的的的时时时时间间间间复复复复杂杂杂杂度为度为度为度为O(n*e)O(n*e)； 当当当当图图图图g g采采采采用用用用邻邻邻邻接接接接矩矩矩矩阵阵阵阵方方方方式式式式存存存存储储储储，由由于于找找每每个个顶顶点点的的邻邻接接点点时
84、时，内内内内循循循循环环环环次次次次数数数数等等等等于于于于n n，因因因因此此此此广广广广度度度度优优优优先先先先搜搜搜搜索索索索算算算算法法法法的的的的时间复杂度为时间复杂度为时间复杂度为时间复杂度为O(nO(n2 2) )。 腻讣找迢忌凋澈函怕沥盔县咱瑞播珐猩贱瓷蒋咳块淡剧射寒灌迂折烤择压图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 82非连通图的广度优先搜索非连通图的广度优先搜索非连通图的广度优先搜索非连通图的广度优先搜索： 与与非非连连通通图图的的深深度度优优先先搜搜索索一一样样，非非连连通通的的或或非非强强连连通通图图的的广广度度优优先先搜搜索索从从图
85、图中中某某一一个个顶顶点点出出发发，也也不不能能访访问问到到图图中中所所有有顶顶点点，而而只只能能访访问问到到一一个个连连通通子子图图（既既连连通通分分量量）或或只只能能访访问问到到一一个个强强连连通通子子图图（既既强连通分量）。强连通分量）。 遍遍历历算算法法实实现现时时，对对所所有有顶顶点点进进行行循循环环，反反复复调调用用连连通通图图的的广广度度优优先先搜搜索索遍遍历历算算法法即即可可。具具体体可可以以表表示如下：示如下：讳语维湍搀拈碳亡晒茁权陪呢蛋絮丙渣辅缕磁陪漂荒聪浓陨躲状繁及自虐图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 83for(int i=1;
86、i=n;i+) if(!visitedi) bfs(i) ; 分析上述过程，每个顶点至多进一次队列。遍历分析上述过程，每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接图的过程实质上是通过边或弧找邻接 点的过程。因此点的过程。因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍广度优先搜索遍历图的时间复杂度和深度优先搜索遍广度优先搜索遍历图的时间复杂度和深度优先搜索遍广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之历相同，两者不同之历相同，两者不同之历相同，两者不同之 处仅仅在于对顶点访问的顺序不处仅仅在于对顶点访问的顺序不处仅仅在于对顶点访问的顺序不处仅仅在于对顶点访
87、问的顺序不同同同同。 颜义齿练地絮哪蜡幂如字谐座约锄傈镀兼哪栗蛇徽营天委死朱抖瓦惟童冻图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 84 10.1 图的概念 10.2 图的存储 10.3 图的遍历 10.4 生成树和最小生成树 10.5 最短路径 10.6 有向无环图的应用第10章 图及其应用及嘿册毙床旧拿隘蔚魄袒相炳寿倚窑雕枣与迢粪科信涯盅襄碟袱恐僻笔少图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 85 深深度度优优先先及及广广度度优优先先遍遍历历图图的的过过程程中中，所所经经经经过过过过的的的的边边边边的的的的集集集集合合合合和和
88、和和顶顶顶顶点点点点集集集集合合合合，一一起起构构成成连连通通图图的的极极极极小小小小连连连连通通通通子子子子图图图图。它是连通图的一颗生成树。它是连通图的一颗生成树。生生生生成成成成树树树树：是是一一个个极极小小连连通通子子图图，它它含含有有图图中中全全部部顶顶点点，但只有但只有n-1n-1条边。条边。 由由深深度度优优先先搜搜索索遍遍历历得得到到的的生生成成树树，称称为为深深度度优优先先生生成成树树，由由广广度度优优先先搜搜索索遍遍历历得得到到的的生生成成树树，称称为为广广度优先生成树。度优先生成树。滦辉虑茧怀缸赵昨袭林失扇比厦美瞳菩狂珊售污趣抹焰糊未牡灯殷钮塞见图及其应用(new)图及其
89、应用(new)第第10章章 图及其应用图及其应用 86例：画出下图的生成树例：画出下图的生成树例：画出下图的生成树例：画出下图的生成树DFS生生成成树树v0v1v2v4v4v3邻接表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFS生生成成树树v0v1v3v2v4漏叭董盒庙肖沦扎痞诚埔嚷君族挖绊驾乔采黔毯歪阔蘸肿弥翌盔幂脖断悟图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 87最小生成树最小生成树最小生成树最小生成树 一一般般情情况况下下，若若图图中中的的每每条条边边给给定定了了权权值值，这这时时，我我们们所所关关心心的的不不是是生
90、生成成树树，而而是是生生成成树树中中边边上上权权值值之之和和。若若若若某某某某生生生生成成成成树树树树中中中中每每每每条条条条边边边边上上上上权权权权值值值值之之之之和和和和达达达达到到到到最最最最小小小小，称称称称其其其其为为为为最最最最小小小小代代代代价价价价生生生生成成成成树树树树（Minimum Minimum Cost Cost Spanning Spanning TreeTree），简称为简称为简称为简称为最小生成树最小生成树最小生成树最小生成树(MST)(MST)。可以看出：可以看出：可以看出：可以看出： 图的生成树不是唯一的。图的生成树不是唯一的。 当按深度和广度优先搜索当按深
91、度和广度优先搜索法进行遍历就可以得到两种不同的生成树。法进行遍历就可以得到两种不同的生成树。玄添靶赢名谓哮辗便邪瞪瘴恨杖酒状鸟胰楷核丝出暴嫡添邓素团卜坡撬熄图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 88 例：例：例：例：连通网连通网 的生成树。的生成树。 4132656 66 66 65 55 55 52 21 13 34 44132656 66 65 55 54 4(a)4132656 62 21 13 34 4(b)4132655 52 21 13 34 4(c) 其中其中(a)的权值之和为的权值之和为26, (b)的权值之和为的权值之和为16, (c)的
92、的权值之和为权值之和为15, 可以证明可以证明(c)为一棵最小生成树。为一棵最小生成树。工鞭纸鲍盎墅脾玛厚嘎膝旬佩拔保挂乾浓充侠石蝶傍摈敦拨晌貌孵吹颊昌图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 89欲在欲在n个城市间建立通信网，则个城市间建立通信网，则n个城市应铺个城市应铺n-1条线条线路；但因为每条线路都会有对应的经济成本，而路；但因为每条线路都会有对应的经济成本，而n个城个城市可能有市可能有n(n-1)/2 条线路，那么，条线路，那么，如何选择如何选择n1条线路，条线路，使总费用最少？使总费用最少？典型用途：典型用途：典型用途：典型用途：数学模型：数学模型
93、：数学模型：数学模型：顶点顶点表示城市，有表示城市，有n个；个；边边表示线路，有表示线路，有n1条；条；边的权值边的权值表示线路的经济代价；表示线路的经济代价；连通网连通网表示表示n个城市间通信网。个城市间通信网。显然此连通网是显然此连通网是一个一个生成树！生成树！滓嚣惨银谅蚂饯怜琶陶阂坯次警契臃脾韵疾帽殖翱带雹星汛偷刑膀炎垛坑图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 90 如如何何选选择择其其中中的的n-1条条线线路路(边边)在在n个个城城市市间间建建成全都能相互通讯的网成全都能相互通讯的网, 并且总的建设花费为最小并且总的建设花费为最小? 这就是求该网络的
94、最小生成树问题。这就是求该网络的最小生成树问题。 杯渴媚逃豺塑贼第台剿直营闪颖戎鲍朝泽曝灵友祖叙航涡牡冠榜汉袭靡瘴图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 91最小生成树最小生成树最小生成树最小生成树有如下重要有如下重要性质性质性质性质(MST(MST性质性质性质性质) )： 设设 N=(V, VR) 是是一一连连通通网网，U 是是顶顶点点集集V的的一一个个非非空空子子集集。 若若（u , v）是是一一条条具具有有最最小小权权值值的的边边， 其其中中uU， vV-U， 则则存存在在一一棵棵包包含含边边（u , v）的的最小生成树。最小生成树。 我我们们可可以以
95、利利用用MST性性质质来来生生成成一一个个连连通通网网的的最最小小生生成成 树树 。 普普普普 里里里里 姆姆姆姆 （ PrimPrim） 算算算算 法法法法 和和和和 克克克克 鲁鲁鲁鲁 斯斯斯斯 卡卡卡卡 尔尔尔尔（KruskalKruskal）算法）算法）算法）算法便是利用了这个性质。便是利用了这个性质。 阎盆指搏烧剖珐混藏廓岔油郸然霞宦切辗恍窖疗凄仓税筑蝉答立栓撒申悸图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 92 1. 普里姆算法普里姆算法基本思想：基本思想：基本思想：基本思想： 每每一一次次在在满满足足如如下下条条件件的的边边中中，选选一一条条最最小
96、小权权值值的边。的边。 条件：条件：条件：条件：一端顶点已入选，而另一端未选。一端顶点已入选，而另一端未选。淮亦郸恼呼兽勾乐刻茧改规缠频尤舆车筐獭蚌醚识逢瓮圣疟乱吊汁却募暑图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 93具体描述如下：具体描述如下：具体描述如下：具体描述如下： 假设假设N=(V, VR)是连通网，是连通网，TE为最小生成树中边的为最小生成树中边的集合。集合。（1） 初始初始U=u0(u0V), TE= （2） 在所有在所有uU, vV-U的边中选一条代价最小的的边中选一条代价最小的边边(u0,v0 )并入集合并入集合TE，同时将，同时将v0并入并
97、入U； （3） 重复（重复（2），）， 直到直到U=V为止。为止。 此时，此时，TE中必含有中必含有n-1条边，则条边，则T=（V，TE）为）为N的的最小生成树。最小生成树。 褒疲兄夷僚汇汀偶定硼鱼吩诚幼快来杨勾哥湿樊通股尔蔷比惋占希湛思踪图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 944132656 66 66 65 55 55 52 21 13 34 4例：例：例：例：利用普里姆算法从利用普里姆算法从v1开始构造最小生成树。开始构造最小生成树。16 66 66 65 55 55 52 21 13 34 41 13 31 13 35 55 52 22 24 4
98、4 46 6砖姻卫橙浪淑撰驾谨专锡隆御啦侠栗丢抄乒犯管凹凡歼探卒减隐神帮贼权图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 95 可以看出，可以看出， 普利姆算法逐步增加普利姆算法逐步增加U中的顶点，中的顶点， 可称为可称为“加点加点法法”。 为了实现这个算法需要设置一个为了实现这个算法需要设置一个辅助数组辅助数组辅助数组辅助数组closedge closedge ，以记录，以记录，以记录，以记录从从从从U U到到到到V-UV-U具有最小代价的边。具有最小代价的边。具有最小代价的边。具有最小代价的边。对每个顶点对每个顶点vV-U，在辅助数组，在辅助数组中存在一个分量
99、中存在一个分量closedgev,它包括两个域它包括两个域adjvexadjvex和和lowcostlowcost, 其中其中lowcost存储该边上的权，存储该边上的权， 显然有显然有 closedgev.lowcost=Min(cost(u,v)|uU) struct VertexData adjvex; VertexData adjvex; int lowcost; int lowcost; closedgeMAX_V_N; / / 求最小生成树时的辅助数组求最小生成树时的辅助数组求最小生成树时的辅助数组求最小生成树时的辅助数组 辫求辈厂玩噎装雁设眯竭呛躬你孤搅镑喝壬裳各爸辨疤熬腐垃吐毒
100、束嗣心图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 96 typedef structstruct VertexData VertexData vexsMAX_V_N;vexsMAX_V_N; / /顶顶顶顶点点点点向向向向量量量量 ArcNode ArcNode arcsMAX_V_NMAX_V_N;arcsMAX_V_NMAX_V_N; / /邻邻邻邻接接接接矩矩矩矩阵阵阵阵 int vexnum, arcnum;int vexnum, arcnum; / /图的顶点数和弧数图的顶点数和弧数图的顶点数和弧数图的顶点数和弧数 GraphKind kind;Gra
101、phKind kind; / /图的种类标志图的种类标志图的种类标志图的种类标志 AdjMatrix; /(Adjacency Matrix Graph)/(Adjacency Matrix Graph) 荫卵辊爪伟族剑荫酞酪席剩绑何惑掐臀媳沉枣子苑谬渠彼瓜南夸啡穆上昔图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 97typedef struct ArcNodestruct ArcNode AdjType adj; AdjType adj; / / AdjTypeAdjType是是是是顶顶顶顶点点点点关关关关系系系系类类类类型型型型，对对对对无无无无权权权权图图图
102、图，用用用用1 1或或或或0 0表表表表示是否相邻；对带权图，则为权值类型示是否相邻；对带权图，则为权值类型示是否相邻；对带权图，则为权值类型示是否相邻；对带权图，则为权值类型 InfoType *info;InfoType *info; / /该弧相关信息的指针该弧相关信息的指针该弧相关信息的指针该弧相关信息的指针 ArcNode; 取瘪贯温皋哦荷泞缓嘛骚酶肠总言聪息赏咒土梭火瞻妈酉猜兵褂年尾泰霓图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 98假设开始顶点就选为顶点假设开始顶点就选为顶点1，首先有，首先有U=1，U-V=2，3，4，5，6i123 3456cl
103、osedgei.adjvex111111closedgei.lowcost061 15 4132656 66 66 65 55 55 52 21 13 34 44132656 65 51 1 for (i=1; i=gn.vexnum; i+) closedgei.adjvex=k0; / k0U closedgei.lowcost=gn.arcsk0i.adj; 枚豪殆蚜釉千拇喜亮经策目柑律决肮刑阳蒜玉莆讲慑枕草淀椒马眺缔虑作图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 99i123456 6closedgei.adjvex133133closedgei.low
104、cost0505 64 4 在顶点在顶点在顶点在顶点k1k1并入并入并入并入U U之后，之后，之后，之后， 更新更新更新更新closedgeclosedgei i for ( i=1 ; i=gn.vexnum; i+) if ( gn.arcsk1i.adj closedgei.lowcost) closedgei.lowcost= gn.arcsk1i.adj; closedgei.adjvex=k1; 4132656 65 55 51 14 4U=1, 3，U-V=2，4，5，6i123 3456closedgei.adjvex111111closedgei.lowcost061 15
105、趴亥决面料谱骄涛霓句尾宰祝惰品刊寐山悯掳灯抉属虑篙淀埠噶类部玩洞图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 100i1234 456closedgei.adjvex133636closedgei.lowcost0502 2 60 U=1, 3, 6，U-V=2，4，52 24132656 65 51 14 4i123456 6closedgei.adjvex133133closedgei.lowcost0505 64 4 慈除势摆烦颇效元畦砒醋扯到屿循燎赴透形皖梢锐田爬矽吸父匆捡衙某围图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 1
106、01i1234 456closedgei.adjvex133636closedgei.lowcost0502 2 60 4132656 65 51 14 42 2U=1, 3, 6, 4， U-V=2，5i12 23456closedgei.adjvex133436closedgei.lowcost05 50060 纽练惜沧奴店陷鉴谴狭描买烯直照哨据霍投朱镣痒咸悟吗窍槐峨戎裸呆牲图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 102i123456closedgei.adjvex123426closedgei.lowcost0000 3 30 U=1, 3, 6, 4
107、, 2，U-V=52 24132655 51 14 43 3i12 23456closedgei.adjvex133436closedgei.lowcost05 50060 委缔歼户颁蛔址木握滨舅更捕怔誓际卧吃蓑蔼赦治忠屁窖曲厄探直签土垒图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 103U=1, 3, 6, 4, 2, 5， U-V= i123456closedgei.adjvex123456closedgei.lowcost000000 4132655 52 21 13 34 4i123456closedgei.adjvex123426closedgei.lo
108、wcost0000 3 30 靡拉救访哈寓找簿姜霜汁急眯话喂嗽疡凉避摩实杭涵咬茂俊芬傲阜绅担驱图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 104普里姆算法可描述如下：普里姆算法可描述如下：普里姆算法可描述如下：普里姆算法可描述如下： struct VertexData adjvex; VertexData adjvex; int lowcost; int lowcost; closedgeMAX_V_N; / / 求最小生成树时的辅助数组求最小生成树时的辅助数组求最小生成树时的辅助数组求最小生成树时的辅助数组MSpTree-Prim(AdjMatrix gn,
109、VertexData u)/ /从从从从顶顶顶顶点点点点u u出出出出发发发发， 按按按按普普普普里里里里姆姆姆姆算算算算法法法法构构构构造造造造连连连连通通通通网网网网gn gn 的的的的最最最最小小小小生生生生成成成成树树树树， 并输出生成树的每条边并输出生成树的每条边并输出生成树的每条边并输出生成树的每条边啃处匀闯贷簧桑瓜偿锁挡蒸孵杭箱佯齿队鳃期涪鄙丫坍嘲衍唆沟品印俄榔图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 105 k=LocateVertex(gn, u); / k/ k为顶点为顶点为顶点为顶点u u的位置的位置的位置的位置 closedgek.lo
110、wcost=0; / /初始化，初始化，初始化，初始化， U=u U=u for (i=0; ign.vexnum; i+) if ( i! =k) / /对对对对V-UV-U中的顶点中的顶点中的顶点中的顶点i, i,初始化初始化初始化初始化closedgeiclosedgei closedgei.adjvex=u; closedgei.lowcost=gn.arcski.adj; for (e=1; e=gn.vexnum-1; e+) / /找找找找n-1n-1条边条边条边条边(n= gn.vexnum) (n= gn.vexnum) k0=Minium(closedge); / clos
111、edge / closedgek0k0中存有当前最小边（中存有当前最小边（中存有当前最小边（中存有当前最小边（u0, v0u0, v0）的信息）的信息）的信息）的信息 u0= closedgek0.adjvex; / u0/ u0U U v0= gn.vexsk0 / v0/ v0V-UV-U瞪健意迎猫同敌斌帆港页洞历帜苍僚容记奏荒汇蒂东偿贰啸请坯含弱绦产图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 106 printf(u0, v0); / /输出生成树的当前最小边输出生成树的当前最小边输出生成树的当前最小边输出生成树的当前最小边(u0, v0)(u0, v0)
112、 closedgek0.lowcost=0; / /将顶点将顶点将顶点将顶点v0v0纳入纳入纳入纳入U U集合集合集合集合 for ( i=0 ; ivexnum; i+) / /在顶点在顶点在顶点在顶点v0v0并入并入并入并入U U之后，之后，之后，之后， 更新更新更新更新closedgeclosedgei i if ( gn.arcsk0i.adj closedgei.lowcost) closedgei.lowcost= gn.arcsk0i.adj; closedgei.adjvex=v0; 闪判份油扬蒋舱布喻阀膛享磁雕茨赎食猪亲以戳歌履意簿半件狗配宽茫舅图及其应用(new)图及其应用
113、(new)第第10章章 图及其应用图及其应用 107 2. 克鲁斯卡尔算法克鲁斯卡尔算法 基基基基本本本本思思思思想想想想：每每一一次次在在满满足足如如下下条条件件的的边边中中，选选一一条条权权值最小的边。值最小的边。 条件：条件：条件：条件：与已选边不构成回路。与已选边不构成回路。 氛鸟欠探草帜钉惧乃想抉逻皱候筏波族酋摇达蠕袜瘪惭具护怪尘仇域诛丹图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 1084132651616191918186 65 56 62121141433331111例：例：例：例：利用克鲁斯卡尔算法构造最小生成树。利用克鲁斯卡尔算法构造最小生成树
114、。413265161618186 65 56 614141111求科绿倚禁份惦涩淑难廷讶斯校捶谊氢嘲锣蝉嘘嘶克坊歌傅稼徽秉滩娠开图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 109 可可以以看看出出，克克鲁鲁斯斯卡卡尔尔算算法法逐逐步步增增加加生生成成树树的的边边， 与与普普里里姆姆算算法法相相比比，可可称称为为“加加边边法法”。 雌笔烫庶粟帖秸倍骋新避慢烙迪烛狐控俘梨晴炊陪跃雇瘴传埃程乍卑桨绊图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 110 10.1 图的概念 10.2 图的存储 10.3 图的遍历 10.4 生成树和最小生成树
115、 10.5 最短路径 10.6 有向无环图的应用第10章 图及其应用伎贿潞狐霓福优逸祷陕坍硬审究杠溢标承潮遭侯赶筒叠跳早谢颖莲白曾昔图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 111典型用途：典型用途：典型用途：典型用途：求图的最短路径问题用途很广，求图的最短路径问题用途很广， 例如：交通网络中常常提出这样的问题：从甲地到例如：交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通乙地之间是否有公路连通? 在有多条通路的情况下，在有多条通路的情况下，哪一条路最短哪一条路最短? 交通网络可用带权有向图来表示。顶点表示城市名交通网络可用带权有向图来表示。顶点表
116、示城市名称，边表示两个城市有路连通，边上权值可表示两城称，边表示两个城市有路连通，边上权值可表示两城市之间的距离、交通费或途中所花费的时间等。市之间的距离、交通费或途中所花费的时间等。 如何能够使一个城市到另一个城市的运输时间最短如何能够使一个城市到另一个城市的运输时间最短或运费最省？这就是一个求两座城市间的最短路径问或运费最省？这就是一个求两座城市间的最短路径问题。题。曲勘婶醒愿供支豁琢敬锰啤楼脐秦族察赊受枪滚姿遍澄设劲紊船磕套饯站图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 112问题抽象：问题抽象：问题抽象：问题抽象：在在带权有向图带权有向图带权有向图带权有
117、向图中中A点（源点）到达点（源点）到达B点（终点（终点）的多条路径中，寻找一条各边权值之和最小的路点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径径，即最短路径（注：最短路径与最小生成树不同，路径上不一定包（注：最短路径与最小生成树不同，路径上不一定包（注：最短路径与最小生成树不同，路径上不一定包（注：最短路径与最小生成树不同，路径上不一定包含含含含n n个顶点）个顶点）个顶点）个顶点） 本节讨论带权有向图（有向网）的两种最短路本节讨论带权有向图（有向网）的两种最短路径问题：径问题：（1）求一结点到其它结点的最短路径）求一结点到其它结点的最短路径（2）求任意两点间的最短路径）求任意
118、两点间的最短路径何隘鳞德惟肿漏轴吱碉裹败诵换寓沾纵冈网保叁灌掠始坤雀营臣门蛮津妈图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 113 10.5.1 单源最短路径 10.5.2 任意两点间的最短路径10.5 最短路径筐星迭甚霹哼娩坝署拳厦霍央茄瑚窘痪超摊彰逾赖趣卸锭刘突窑器屏楷哨图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 114求某一顶点到其它各顶点的最短路径求某一顶点到其它各顶点的最短路径求某一顶点到其它各顶点的最短路径求某一顶点到其它各顶点的最短路径: : 设从顶点设从顶点v1出发出发, 找从它到图中所有其它各顶点的最找从它到图中
119、所有其它各顶点的最短路径。短路径。 迪杰斯特拉迪杰斯特拉(Dijkstra)提出了一个提出了一个按路径长按路径长按路径长按路径长度递增的顺序产生最短路径度递增的顺序产生最短路径度递增的顺序产生最短路径度递增的顺序产生最短路径的方法。的方法。惧奇骏牙咋弘宠博嫁仆萎置你崩倘历镐静拖臭书耳匣静佐裔仍驳未灌跋梢图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 115算法的基本思想是算法的基本思想是算法的基本思想是算法的基本思想是: : : : 把图中顶点集合分成两组，第一组为集合把图中顶点集合分成两组，第一组为集合S，存放，存放已求出其最短路径的顶点，第二组为尚未确定最短路已
120、求出其最短路径的顶点，第二组为尚未确定最短路径的顶点集合是径的顶点集合是V-S（用（用U表示），其中表示），其中V为网中所有为网中所有顶点集合。顶点集合。 按最短路径长度递增的顺序逐个把按最短路径长度递增的顺序逐个把U中的顶点加中的顶点加到到S中，直到中，直到S中包含全部顶点，而中包含全部顶点，而U为空。为空。剁请仪栅爆阜屠懂引殷苦剪萨猜陋随盼匿振窿匙搁羽飘缚趁自疚龄辐阶气图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 116 在加入的过程中，总保持从源点在加入的过程中，总保持从源点v到到S中各顶点的中各顶点的最短路径长度不大于从源点最短路径长度不大于从源点v到到U
121、中任何顶点的最短路中任何顶点的最短路径长度。径长度。 此外，每个顶点对应一个距离，此外，每个顶点对应一个距离，S中的顶点的距中的顶点的距离就是从离就是从v到此顶点的最短路径长度，到此顶点的最短路径长度，U中的顶点的距中的顶点的距离从离从v到此顶点只包括到此顶点只包括S中的顶点为中间顶点的当前最中的顶点为中间顶点的当前最短路径长度。短路径长度。 廖朔兴羹企享略拌绝诞熬忘担坏氏恃凹脚犊疥椽鞋显濒躺魄辽袁豌措洱渐图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 117算法分析：算法分析：算法分析：算法分析：我们可以我们可以将图中的顶点分为两组将图中的顶点分为两组将图中的顶点
122、分为两组将图中的顶点分为两组： S 已求出的最短路径的终点集合已求出的最短路径的终点集合(开始为开始为v0) V-S 尚未求出最短路径的顶点集合尚未求出最短路径的顶点集合 (开始为开始为Vv0的全部结点的全部结点)。 按最短路径长度的递增顺序逐个将第二组的顶点加按最短路径长度的递增顺序逐个将第二组的顶点加入到第一组中。入到第一组中。陷芽双怕扯肺热兆虞展叉凹誓碾盒砷涅旦棍蚕慢缠氏加篆绢踊触捎示擎匙图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 118 引引引引进进进进辅辅辅辅助助助助向向向向量量量量dist dist ，它它的的每每一一个个分分量量distidisti
123、表表表表示示示示已已已已经经经经找找找找到到到到的的的的且且且且从从从从开开开开始始始始点点点点v0v0到到到到每每每每一一一一个个个个终终终终点点点点vi vi 的的的的当当当当前前前前最最最最短短短短路路路路径径径径的的的的长长长长度度度度。 它它的的初初态态为为：如如果果从从v0到到vi 有有弧弧，则则disti 为弧的权值；否则，为弧的权值；否则，disti 为为 。 设置一个路径向量设置一个路径向量设置一个路径向量设置一个路径向量pathnpathn，其中，其中pathi为从源点到为从源点到vi点的最短路径上该点的前趋顶点。点的最短路径上该点的前趋顶点。 找下一条长度次短的路径找下一
124、条长度次短的路径找下一条长度次短的路径找下一条长度次短的路径 假设该次短路径的终点是假设该次短路径的终点是vk，则这条路径可能是，则这条路径可能是(v0 , vk) 或者是或者是(v0 , vj , vk)乔粥火近巧烯栓劝楚鞋淀臃雪骡鸿藻油胶袍弓衅顾芒驹障官拯灵匿巡寇填图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 119V0V3V2V4V1V5455010102015153353015例：例：例：例：SV0 U V-S V1 ,V2 , V3 , V4 , V5 dist1dist2dist3dist4dist5V0到到Vi的距离的距离disti:初始：初始：50
125、1045V0式悄吏眷凄旋帧嵌津介佩竭十烙呵影递纪听汐铅带通归取疆恶左嘱毯马虐图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 120V0V3V2V4V1V5455010102015153353015例：例：例：例：SV0 ,V V2 2 U V-S V1, V3 , V4 , V5 dist1dist2dist3dist4dist5V0到到Vi的距离的距离disti:501045V0SV0 U V-S V1 ,V2 , V3 , V4 , V5 V21010接下来，接下来， V0到到Vi的距离的距离是是min(V0 Vi， V0 V V2 2 Vi)腹邪港圈嚷宾嫩纷啄
126、亩辗沧看墒敢痊舞砸万栓研些馈森庞翔陋待范稀桩学图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 121V0V3V2V4V1V5455010102015153353015例：例：例：例：SV0 ,V V2 2 U V-S V1, V3 , V4 , V5 dist1dist2dist3dist4dist5V0到到Vi的距离的距离disti:50101045V0V21010V0 V1 为为50 V0 V V2 2 V1 为为V0 V3为为 V0 V V2 2 V3为为25 2525V0 V4为为45 V0 V V2 2 V4为为 V0 V5为为 V0 V V2 2 V5为
127、为 SV0 ,V V2 2 , V V3 3 U V-S V1, V4 , V5 1515V3接下来，接下来， V0到到Vi的距离的距离是是min(V0 Vi， V0 V V3 3 Vi)注意：注意： V0到到V V3 3的的距离距离是是2525亡垫梯循躺朗笼睹切脏婉蔬慎窖赤脆舒鞠音荔踢堡锑频睬劳贡襟刮踌伎饱图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 122V0V3V2V4V1V5455010102015153353015例：例：例：例：dist1dist2dist3dist4dist5V0到到Vi的距离的距离disti:50101045V0V21010V0 V
128、1 为为50 V0 V V3 3 V1 为为40402525V0 V4为为45 V0 V V3 3 V4为为60 V0 V5为为 V0 V V3 3 V5为为 SV0 ,V V2 2 , V V3 3 U V-S V1, V4 , V5 1515V34040SV0 ,V V2 2 , V V3 3 , V V1 1 U V-S V4 , V5 V11515接下来，接下来， V0到到Vi的距离的距离是是min(V0 Vi， V0 V V1 1 Vi)注意：注意： V0到到V V1 1的的距离距离是是4040藉厢舌拟长支雄贮粳锣很镣劳好馅颇叁厅芋桥渝敬负槽努敛夷镶唤函喇晕图及其应用(new)图及其
129、应用(new)第第10章章 图及其应用图及其应用 123V0V3V2V4V1V5455010102015153353015例：例：例：例：dist1dist2dist3dist4dist5V0到到Vi的距离的距离disti:101045V0V210102525V0 V4为为45 V0 V V1 1 V4为为50 V0 V5为为 V0 V V1 1 V5为为 1515V34040SV0 ,V V2 2 , V V3 3 , V V1 1 U V-S V4 , V5 V11515SV0 ,V V2 2 , V V3 3 , V V1 1 , V V4 4 U V-S V5 接下来，接下来， V0到
130、到Vi的距离的距离是是min(V0 Vi， V0 V V4 4 Vi)注意：注意： V0到到V V4 4的的距离距离是是4545V44545仑骂札澄纽我旱寒累燕纺姆贰守壬昼恤挖卸淘柄薯群哩杯碗级绩炒慎嘉营图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 124V0V3V2V4V1V5455010102015153353015例：例：例：例：dist1dist2dist3dist4dist5V0到到Vi的距离的距离disti:10104545V0V210102525V0 V5为为 V0 V V4 4 V5为为 1515V34040V11515SV0 ,V V2 2 ,
131、V V3 3 , V V1 1 , V V4 4 U V-S V5 V5SV0 ,V V2 2 , V V3 3 , V V1 1 , V V4 4 , V V5 5 U V-S 算法结束。算法结束。V44545常堂罗急约啥题慎曝仆吮霖沁炮请拐苍套屁饶兄尧颧九其句匀厉谦享翠黔图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 125例：例：例：例：则：顶点则：顶点V0到其余各顶点到其余各顶点Vi的最短路径分别为：的最短路径分别为：:V0到到V1的最短路径的最短路径是是V0 V2 V3 V1 ， 距离值为距离值为4040V0到到V2的最短路径的最短路径是是V0 V2， 距
132、离值为距离值为1010V0到到V3的最短路径的最短路径是是V0 V2 V3 ， 距离值为距离值为2525V0到到V4的最短路径的最短路径是是V0 V4 ， 距离值为距离值为4545V0到到V5无最短路径无最短路径.V0V3V2V4V1V5455010102015153353015V0V210101515V3V11515V5V44545钵侗爪轿妆诗蝗孜籍斌裂奢措资浑憨租忠圆姥掘湾尉劝垂狞算淘烈渤掺烦图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 126迪杰斯特拉算法实现的主要步骤如下：迪杰斯特拉算法实现的主要步骤如下：迪杰斯特拉算法实现的主要步骤如下：迪杰斯特拉算法实
133、现的主要步骤如下： (1)g为用邻接矩阵表示的带权图。为用邻接矩阵表示的带权图。 Sv0 Sv0 ， disti= g.arcsv0vi disti= g.arcsv0vi； 将将v0到其余顶点到其余顶点的路径长度初始化为权值；的路径长度初始化为权值；(2) 比较比较比较比较distidisti，找到顶点，找到顶点，找到顶点，找到顶点vkvk，使得，使得 distk = Mindisti, i , kV；将将将将vkvk并入并入并入并入S S集集集集纽返土伤歪兼剖晤亡翔募绪敝雾夕桶巳陨挟凶谊曳赦抚郑峦淫挤汉繁琼肃图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 127
134、(3) 比较比较比较比较与与与与的大小的大小的大小的大小，若，若 distk+g.arcskidisti 则将则将disti修改为修改为 distk+ g.arcski ； 同时修改同时修改pathi的值。的值。(4) 重复重复重复重复(2)(2)、(3) n-1(3) n-1次次次次，即可按最短路径长度的递增，即可按最短路径长度的递增顺序，逐个求出顺序，逐个求出v0到图中其它每个顶点的最短路径。到图中其它每个顶点的最短路径。 寨碑睦柏闯渔林豪踞诣群肩瘁吩周爪床枷失跑榜具敝嗅帮婿征尺呀帮端晌图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 128求最短路径的算法描述如
135、下：求最短路径的算法描述如下： WeightType distn; int pathn , VertexSet sn; / s为已找到最短路径的终点集合为已找到最短路径的终点集合,若若si=1,则则is; /pathi中存放顶点中存放顶点i的当前最短路径上该点的前趋顶点的当前最短路径上该点的前趋顶点; /disti中存放顶点中存放顶点i的当前最短路径长度的当前最短路径长度ShortestPath_DJS(AdjMatrix g, int v0) for(i =0; ig.vexnum ; i+) /初始化初始化disti,pathi disti=g.arcsv0i; if(disti!=MAX
136、) pathi=v0; else pathi = -1; 革筛洪思刀玩暂苏游怒楔床窜事便弥贵麓照炼堆武防纬忍诌韵虱褪弟蠢喝图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 129 for(i =0; ig.vexnum ; i+) si=0;for(i =0; ig.vexnum ; i+) si=0; sv0=1; distv0= 0;sv0=1; distv0= 0; for(i =1; ig.vexnum ; i+) min = MAX; for(j =0; jg.vexnum ; j+)for(j =0; jg.vexnum ; j+) if(!sj&dist
137、jmin) min=distj ; k=j; if(!sj&distjmin) min=distj ; k=j; sk=1; for(j =0; jg.vexnum ; j+)for(j =0; j distk+g.arcskj ) if ( !sj & distj distk+g.arcskj ) distj = distk +g.arcskj ; distj = distk +g.arcskj ; pathj = k ; pathj = k ; /修正修正disti,pathi 伪膜肺瓤簿纸寂伴犹妥雾叔缚孟离搭郝帧唁艾眼荣琶蚜撩无沁戍拈羊艾院图及其应用(new)图及其应用(new)第第10
138、章章 图及其应用图及其应用 130 for(i =0; ig.vexnum ; i+) printf(“%f %dn”, disti, i ); pre = pathi ; while ( pre != -1) printf(“ %d”, pre ); pre = pathpre ; 该算法的时间复杂度为该算法的时间复杂度为O(n2)矾柄俐寨论铜甫革铆播碧官耍氓迎翠汤滥襟陨镭耕杂退掐框豺告陨浩孽嚎图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 131 10.5.1 单源最短路径 10.5.2 任意两点间的最短路径10.5 最短路径罩凑绿痊鸵恼霄禹讹饯换阑鼻茨荡挛艘斜
139、乏宿赡汞府窝煞钡暖赞讹摩痉仔图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 132 求每一对顶点之间的最短路径的一种方法是反复执求每一对顶点之间的最短路径的一种方法是反复执行行n次次Dijkstra算法算法, 每次执行以一个顶点为源点每次执行以一个顶点为源点, 求得求得从该顶点到其它各顶点的最短路径从该顶点到其它各顶点的最短路径; 其时间复杂度为其时间复杂度为O(n3)。下面介绍一种形式简洁的弗罗伊德算法其时间复。下面介绍一种形式简洁的弗罗伊德算法其时间复杂度也为杂度也为O(n3)。1. 弗罗伊德算法的步骤弗罗伊德算法的步骤 弗罗伊德弗罗伊德(Floyd)算法的基本
140、思想如下：算法的基本思想如下： 模荔暑内杠伤夯睡护悯畏署催迈妊找襟刘答湘瞄扇归密为刺烂苹局牺沮走图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 133 对给定的有向网G=(V , E) i , jV 用邻接矩阵arcs表示有向网。若 i 到 j 有一条弧，则存在arcsij 为从 i 到 j 的路径长度，但它不一定是从 i 到 j 的最短 路径长度。我们应依次考虑依次考虑 i 到到 j 能否有以顶点能否有以顶点1、2、n 为中间结点的更短路径。为中间结点的更短路径。酞茨验笔规例嵌壤凤笛捞代及旁踌矿销汰诗淆厕灌重谁质杏峦桓庄侧瓜旧图及其应用(new)图及其应用(new
141、)第第10章章 图及其应用图及其应用 134(1) 首先考虑从首先考虑从 i 到到 j是否有以顶点是否有以顶点 1 为中间结点的路径。为中间结点的路径。 即：是否有即：是否有、，若有，则比较，若有，则比较arcsij 与与arcsi1+ arcs1j 较短者为当前所求得的最短路径。较短者为当前所求得的最短路径。 此时应修正此时应修正arcsij 的值，并记下的值，并记下 i 的后继的后继1 此时此时arcsij 的值是从的值是从 i 到到 j 、中间顶点数不大于、中间顶点数不大于 1 时时的最短路径的最短路径居份耐帅悲妈股揍闷禽嘴谰释迪爆椭浑忌骏任午镁把罢独凤藻乱呆芝讲蚌图及其应用(new)图
142、及其应用(new)第第10章章 图及其应用图及其应用 135(2) 其次，考虑从其次，考虑从 i 到到 j 是否有包含顶点是否有包含顶点 2 为中间点的为中间点的路径。路径。若无，则从 i 到 j 的最短路径是(1)步求得的；若若有，则有，则 i 2j 可分解为两条路径：可分解为两条路径：i 2 、2j 这两条路径的最短路径是是在这两条路径的最短路径是是在(1)步求得的步求得的，（即i 2 、2j可分别看作 (1)步中的 i 、j，它们之间有数量不超过 1 的结点） 吏率抵缴汐臃僵籍轮笺睁手疥夹持底拓袁弊临伴彪训罚穷情揖淄滚沉侯镜图及其应用(new)图及其应用(new)第第10章章 图及其应用
143、图及其应用 136 比较比较arcs1ij 与与arcs1i2+ arcs12j 可修可修正正arcs1ij 的值为的值为arcs2ij （它是当前求得的从 i 到 j 、中间顶点数不大于 2 时的最短路径）纸蔫凡丑靛贪殷态群崭茁糖惹赢茅奖里性倘哑啼森软陕伏威营官签店机骏图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 137(3) 依次类推，直到考虑了顶点依次类推，直到考虑了顶点 n 加入当前从加入当前从 i 到到 j 的最短路径的最短路径后，得出最新的最短路径arcsnij 是从 i 到 j 之间经过的顶点数不大于 n 时的最短路径长度现已考虑了所有顶点作为中间点
144、的可能性，因而它必是从 i 到 j 的最短路径。 酪危舶啦烈殴拓须斡盅究痪堑众骇撮截艇糙迹圃泼讫隐涣拌最帅菏溜胳月图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 138由此看出，由此看出，弗罗伊德弗罗伊德(Floyd)算法实际是通过一系列算法实际是通过一系列矩阵矩阵A0 、 A1 、 A2 An 、来实现求解。其中，、来实现求解。其中，Akij 即即arcskij ，表示从，表示从 i 到到 j 之间经过的顶点数之间经过的顶点数k 时时的最短路径长度。的最短路径长度。凌寨益桶锅猪析挖军谨擦嗡愚熊锻戌傻枕测翟瑞魔泽祭孙露漫哗资撼元族图及其应用(new)图及其应用(ne
145、w)第第10章章 图及其应用图及其应用 139 讨论的焦点： 由由Ak-1 求求Ak ijkk-1k-1k-1Ak-1ijAk-1ik Ak-1kj if (Ak-1ik +Ak-1kj Ak-1ij) Akij = Ak-1ik +Ak-1kj 创酚佐七殃嫉秀牛轿绽柏惠责胸龙裳诣帚碎捐混库栓夯辗疑掇窝沼涩贷阁图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 140算法描述如下：算法描述如下： 设置矩阵An+1n+1 记录两点间的路径长度。 设置矩阵pathn+1n+1 记录每一次求得当前两点 i ,j 间最短路径时，i 的后继顶点。算法结束时，由pathij的值可得
146、从 i 到 j 的最短路径上的各个顶点。(1) 初始化初始化An+1n+1 ，使Aij=arcsij 初始化初始化pathn+1n+1 ，若从 i 到 j 有一条弧，则pathij j ,否则pathij 0 。惦睛皖街幢渤纷诛怯蚀炒敬浊席斗删茄捧檀奴约箭侵剂请抛肌嚣怜簿北吏图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 141(2) 做做 n 次迭代，每次均试图将顶点次迭代，每次均试图将顶点 k 扩充到当前求扩充到当前求得的最短路径上，并修改得的最短路径上，并修改 i 的后继顶点号。的后继顶点号。 for ( k=1; k=n; k+ ) for ( i =1;
147、i =n; i + ) for (j =1; jAik+Akj) Aij = Aik+Akj ; pathij = pathik ; 喷揉宝茨籽检用壬瓷坡帅白挖轮刀叉尤吗州家税氰听抱泡汾圈吠停杖窃归图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 142弗罗伊德弗罗伊德(Floyd)算法描述如下：算法描述如下： int pathij; Floyd ( float A n+1 , AdjMatrix g) int i , j, k, next, max = 10000 ; for ( i =1; i =n; i + ) /*初始化path , A0*/ for (j =
148、1; j=n; j+ ) if ( g.arcsij != max ) pathij = j ; else pathij = 0 ; Aij = g.arcsij ; 弥晕蚤绿触搜梅益婆靶彼殿庚殆唆窄枕划舱堕峰谜苦淄洞掖腻停联壶恃味图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 143 for ( k=1; k=n; k+ ) for ( i =1; i =n; i + ) for (j =1; jAik+Akj) Aij = Aik+Akj ; pathij = pathik ; for ( i =1; i =n; i + ) for (j =1; j=n; j+
149、 ) printf(“%f ”, Aij) ; next = pathij ;从沁皱恕垢郊肿劣字衔变却哺帖环崔止溜尘湃硼赘朗柴输咋突菲漳卿颁烃图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 144 if (next = =0 ) printf(“%d to %d no pathn”, i ,j); else printf(“%d ”, i ) ; while( next != j ) printf (“%d ”, next ); next = pathnextj ; printf(“%d ” , j ); 颠姐第玲裁植土羡否贾激蔗播糟天理叠存疵胎桓琢肌首屈虐喇双洼嫂
150、体止图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 145 10.1 图的概念 10.2 图的存储 10.3 图的遍历 10.4 生成树和最小生成树 10.5 最短路径 10.6 有向无环图的应用第10章 图及其应用营咎存缔番酪能矾砂种五旱叫锌即锗缅林都捣垃滚麓馆伞论沟鞍循第灶近图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 146 10.6.1 拓扑排序 10.6.2 关键路径10.6 有向无环图的应用锋标汾桌板遁拿维罕士尉梁毯亭队假细啼短沥蔼刃材侍劲剧丁蛤缄橱饮肺图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应
151、用 147一、一、一、一、AOVAOV网的概念网的概念网的概念网的概念 在一个在一个有向图有向图有向图有向图中，若用中，若用顶点表示活动顶点表示活动顶点表示活动顶点表示活动，有向，有向边表边表边表边表示活动间先后关系示活动间先后关系示活动间先后关系示活动间先后关系，称该有向图叫做顶点表示活动的，称该有向图叫做顶点表示活动的网络网络(Activity On Vertex network)简称为简称为AOV网。网。 在在AOV网中，若从顶点网中，若从顶点i到顶点到顶点j之间存在一条有之间存在一条有向路径，称顶点向路径，称顶点i是顶点是顶点j的前驱，或者称顶点的前驱，或者称顶点j是顶点是顶点i的后继
152、。若的后继。若是图中的弧，则称顶点是图中的弧，则称顶点i是顶点是顶点j的直的直接前驱，顶点接前驱，顶点j是顶点是顶点i的直接后继。的直接后继。勒腋嗓朱誊驾眺房群十分陵瘪琅恳顶袁逞湃牙苍把酥杜氰假激火揣戈芍莱图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 148AOVAOV网实际意义：网实际意义：网实际意义：网实际意义： 现代化管理中现代化管理中, 通常我们把计划、施工过程、生通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为常常被划分成许多较小的子工程，
153、这些子工程称为活活活活动动动动。 在整个工程实施过程中，有些活动开始是以它的在整个工程实施过程中，有些活动开始是以它的所有前序活动的结束为先决条件的，必须在其它有关所有前序活动的结束为先决条件的，必须在其它有关活动完成之后才能开始，有些活动没有先决条件，可活动完成之后才能开始，有些活动没有先决条件，可以以 安排在任意时间开始。安排在任意时间开始。潞妥嗅喜量耻坯程刷雄钢腕迅浪弗涛殿踩炎启汁饵者徊卒驰戊尊硼沃涣啄图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 149 AOV网就是一种可以形象地反映出整个工程中各网就是一种可以形象地反映出整个工程中各个活动之间前后关系的有
154、向图。个活动之间前后关系的有向图。 例如，计算机专业学生的课程开设可看成是一个例如，计算机专业学生的课程开设可看成是一个工工工工程程程程，每一门课程就是工程中的活动。，每一门课程就是工程中的活动。融匿疫全瘤狮黎瞻值滤吱炭寻誉选融佃纠蹲季迭娥钓描宰颧佑劣硬逾羡皇图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 150例：例：例：例：计算机系学生的一些课程间的关系如下表所示。课程编号课程名称先修课程C1高等数学无C2程序设计基础无C3离散数学C1 , C2C4数据结构C2 , C3C5算法语言C2C6编译技术C4 , C5C7操作系统C4 , C9C8普通物理C1C9计算
155、机原理C8鸡蛰镭芭盈箭则辐爽掣坑挖柬蔓僳判隋浓逐究贫峰柑散做稗扭遍伎假单撕图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 151可以看出：可以看出： 其中有些课程的开设有先后关系，有些则没有先后其中有些课程的开设有先后关系，有些则没有先后关系；有先后关系的课程必须按先后关系开设，如开关系；有先后关系的课程必须按先后关系开设，如开设数据结构课程之前必须先学完程序设计基础及离散设数据结构课程之前必须先学完程序设计基础及离散数学，而开设离散数学则必须先并行学完数学、程序数学，而开设离散数学则必须先并行学完数学、程序设计基础课程。设计基础课程。褥徊姜诛舞吮尽框肥皱润洲碎屋蔫
156、沸碰辞妒缩妆与襟谰仗楞雏淑衍恼骄肌图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 152表示课程之间优先关系的有向无环图为： 其中其中, 顶点表示课程顶点表示课程, 有向边表示前提条件。有向边表示前提条件。 若课若课程程vi为课程为课程vj的前行课的前行课, 则必然存在有向边则必然存在有向边 vi, vj 。 潜伤札随艇腿装检臼苔酵林孤朴窄漆殷副国砾芜症阜梧解孵歉湿围赣腊雄图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 153二二二二 拓扑排序拓扑排序拓扑排序拓扑排序 对于有向图对于有向图G=(V,VR)， V中顶点的线性序列（中顶点的线
157、性序列（vi1, vi2, vi3 ，vin）称为）称为拓扑序列。该序列必须满足如下拓扑序列。该序列必须满足如下拓扑序列。该序列必须满足如下拓扑序列。该序列必须满足如下条件：条件：条件：条件： 对序列中任意两个顶点对序列中任意两个顶点vi、vj，若在，若在G中有一条中有一条从从vi到到vj的路径，则在序列中的路径，则在序列中vi必排在必排在vj之前。之前。 构造有向图的一个拓扑序列的过程称为构造有向图的一个拓扑序列的过程称为拓扑排序拓扑排序拓扑排序拓扑排序（Topological sort）磨偏汁魄遍坚那浸若贩辙弛斧腊腕馁依帽溯坛店翌铸抢投沼终笋助羽唐睡图及其应用(new)图及其应用(new)
158、第第10章章 图及其应用图及其应用 154说明：说明：说明：说明：(1) (1) 在在在在AOVAOV网中网中网中网中, ,若不存在回路若不存在回路若不存在回路若不存在回路,则所有活动可排成一则所有活动可排成一则所有活动可排成一则所有活动可排成一个个个个线性序列线性序列,使得每个活动的所有前驱活动都排在该活使得每个活动的所有前驱活动都排在该活动的前面动的前面,那么该序列为那么该序列为拓扑序列拓扑序列拓扑序列拓扑序列.(2) (2) 拓扑序列不是唯一的拓扑序列不是唯一的拓扑序列不是唯一的拓扑序列不是唯一的. .(3) (3) 对对对对AOVAOV网不一定都有拓扑序列网不一定都有拓扑序列网不一定都
159、有拓扑序列网不一定都有拓扑序列. . 在在AOV网中如果出现了有向环，则意味着某项活动网中如果出现了有向环，则意味着某项活动应以自己作为先决条件，这是不对的，工程将无法进应以自己作为先决条件，这是不对的，工程将无法进行。对程序流程而言，将出现死循环。行。对程序流程而言，将出现死循环。 衡斜员贱二窗瞎史抹列正山瘦稿误面充乒度琳札钧卵层晦桔直负惭暮肿讣图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 155(4) (4) 拓扑序列的实际意义是拓扑序列的实际意义是拓扑序列的实际意义是拓扑序列的实际意义是: : 如如果果按按照照拓拓扑扑序序列列中中的的顶顶点点次次序序进进行行
160、每每一一项项活活动动,就就能能够够保保证证在在开开始始每每一一项项活活动动时时,他他的的所所有有前前驱驱活活动动均均已完成已完成,从而使整个工程顺序执行从而使整个工程顺序执行.拿钵似勃属曲揉询葡俩膨削眉份辕橇惜陋痢磅嵌支呛逝寺掏但洼钱破干沸图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 156 问题：问题：问题：问题：怎样求一个怎样求一个AOV网的拓扑序列？网的拓扑序列？拓扑排序的基本思想为：拓扑排序的基本思想为：拓扑排序的基本思想为：拓扑排序的基本思想为： （1）在）在AOV网中选一个入度为网中选一个入度为0的顶点输出；的顶点输出；（2）删除此顶点及该顶点发出来的
161、所有有向边；）删除此顶点及该顶点发出来的所有有向边；（3）重复（）重复（1）、（）、（2）两步，直到）两步，直到AOV网中所有顶网中所有顶点都被输出或网中不存在入度为点都被输出或网中不存在入度为0的顶点。的顶点。 由由上上可可知知，若若在在第第3步步中中，网网中中所所有有顶顶点点都都被被输输出出，则则表表明明网网中中无无有有向向环环，拓拓扑扑排排序序成成功功。若若仅仅输输出出部部分分顶顶点点，网网中中已已不不存存在在入入度度为为0的的顶顶点点，则则表表明明网网中中有有有有向向环，拓扑排序不成功。环，拓扑排序不成功。挤对告陶糜目鱼蕉身衷莲膏巾木邻睡碧瘟椽而十字侨误辛闻罗膊毕盖古打图及其应用(ne
162、w)图及其应用(new)第第10章章 图及其应用图及其应用 157输出拓扑序列为：C5C2C3C4C1C6C8C7C9例：例：例：例：对下图拓扑排序。对下图拓扑排序。C2C1C5C3C4C6C8C7C9一个一个AOV网的拓扑序列不是唯一的网的拓扑序列不是唯一的崖簧正涤嗓咏第初曹莫医四镭假予毯爆头悼疹傅腿舞踩揽劫樱霸树傲室属图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 158拓扑排序算法的实现拓扑排序算法的实现拓扑排序算法的实现拓扑排序算法的实现: : 由由于于有有向向图图的的存存储储形形式式的的不不同同，拓拓扑扑排排序序算算法法的的实实现也不同。现也不同。 1 1
163、） 基于邻接矩阵表示的存储结构基于邻接矩阵表示的存储结构基于邻接矩阵表示的存储结构基于邻接矩阵表示的存储结构 A为有向图为有向图G的邻接矩阵，的邻接矩阵， 则有：则有： 找图找图G中无前驱的顶点中无前驱的顶点 在在在在A A中找到值全为中找到值全为中找到值全为中找到值全为0 0的列；的列；的列；的列； 删除以删除以i为起点的所有弧为起点的所有弧 将矩阵中将矩阵中将矩阵中将矩阵中i i对应的行全部置为对应的行全部置为对应的行全部置为对应的行全部置为0 0。 节孩绎湘肃榆坪容鹏氛廓傀闯谴假夺岂朝盲曝炮源得酌寄嘘僵露购赃怪哩图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用
164、1592 2） 基于邻接表的存储结构基于邻接表的存储结构基于邻接表的存储结构基于邻接表的存储结构 入入度度为为零零的的顶顶点点即即为为没没有有前前驱驱的的顶顶点点， 我我们们可可以以附设一个存放各顶点入度的数组附设一个存放各顶点入度的数组附设一个存放各顶点入度的数组附设一个存放各顶点入度的数组indegree indegree ，于是有：，于是有： 找找G中无前驱的顶点中无前驱的顶点 查找查找查找查找indegreeiindegreei为零的顶点为零的顶点为零的顶点为零的顶点vivi； 删除以删除以i为起点的所有弧为起点的所有弧 对对对对链链链链在在在在顶顶顶顶点点点点i i后后后后面面面面的
165、的的的所所所所有有有有邻邻邻邻接接接接顶顶顶顶点点点点k k，将将将将对应的对应的对应的对应的indegreek indegreek 减减减减1 1。 牟层匪断截办钒益复曾夏疚狂缘吊近凤塌蓟格妇络策抱腊沥氏划炎伎霹旧图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 160 为为了了避避免免重重复复检检测测入入度度为为零零的的顶顶点点，可可以以再再再再设设设设置置置置一一一一个个个个辅辅辅辅助助助助栈栈栈栈，若若某某一一顶顶点点的的入入度度减减为为0，则则将将它它入入栈栈。每每当当输输出出某某一一入入度度为为0的的顶顶点点时时，便便将将它它从从栈栈中中删除。删除。攻闪闽
166、柳哎掏召冷旭宵陆坚朴翠煮己郑模便茄脱壁享阜囤泥蹬柱往嚣香撰图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 16132104例例123456 4 3 5 5vex next 2 5 2 4datalink134256top1 16 6top012230indegree 123456退孽磁双夯郭衡枣简屏据醋闭哗赞挞碰涌痪甸掌莉丹胜饱洒盾桐进矣匙汾图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 16232104例例例例123456 4 3 5 5vex next 2 5 2 4data link1342561 16 6top012230p pi
167、ndegree 1234562 2p p1 1p ptop输出序列：输出序列：6贫缆兄痢完傈腹立庸彬彪姻峨琢沦柿胳祸删雇融访搁舀蔑绅啪顷鞠发迁怒图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 16332104例例例例12345 4 3 5 5vex next 2 5 2 4data link1342561 1top0120p pindegree 1234562 2p p1 1p ptoptop0 04 40 03 31 1p p输出序列：输出序列：61处稳忠孔弊喝窍伺征役诛恤秆女吹右肠函笆袋娄宣卑夫徐侈个坊跪匪锥马图及其应用(new)图及其应用(new)第第10章章
168、 图及其应用图及其应用 16432104例例2345 4 3 5 5vex next 2 5 2 4data link134256top00p pindegree 1234562 2p pp ptop0 04 40 03 31 1输出序列：输出序列：6131 10 02 2绥接褂课絮遏榜薛洁骄刀急狱援罐状恰航演珊蕾丫突号碑唇援仕涟使筛汞图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 16532104例例245 4 3 5 5vex next 2 5 2 4data link134256top00indegree 123456top0 04 40 0输出序列：输出序列
169、：6131 10 02 22扎弧怯光宝杂傀临萄传赔妓巾疫琢砂锯狸追形陨吼弓彩挺偏淡却绅碎酥锑图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 16632104例例45 4 3 5 5vex next 2 5 2 4data link13425600indegree 123456top0 04 40 0输出序列：输出序列：6131 10 02top4p p0 05 5p p厘夺禽人疼斧撂赋腿狰杏狈炒诞扦欣讨姥帜舀联啃昭伪晌肮砷音所饶耐亦图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 16732104例例5 4 3 5 5vex next 2
170、5 2 4data link13425600indegree 123456top0 00 0输出序列：输出序列：6130 02top40 05 55序矿扁姑起勉狄贾聋末霸所逃校蜗屈逛甩掉爹恨屉化桶丧沼株使肥缎哟铅图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 168算法实现：算法实现：算法实现：算法实现： int TopoSort (AdjList G) Stack *S; int indegreeMAX_V_N, i, count, k; ArcNode *p; FindID(G, indegree); /*/*求各顶点入度求各顶点入度求各顶点入度求各顶点入度*/
171、*/ InitStack(S); /*/*初始化辅助栈初始化辅助栈初始化辅助栈初始化辅助栈*/*/阂萌迅猎颜衙氧收陷夸皮八采俞蛙拨草蔫士侥扰糖栈兰乌潭畜姆模角剧谐图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 169 for(i=0; iadjvex; 藐即决油肌幢假碾柏袁诊贡祷馆左榜蒲园执则头造卫憎恼筷雁哼女博史媚图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 170 indegreek-;/ i/ i号顶点的每个邻接点的入度减号顶点的每个邻接点的入度减号顶点的每个邻接点的入度减号顶点的每个邻接点的入度减1 1 if(indegreek
172、=0) Push(S, k); / /若入度减为若入度减为若入度减为若入度减为0 0， 则入栈则入栈则入栈则入栈 p=p-nextarc; /while if (countG.vexnum) return(Error); / /该有向图含有回路该有向图含有回路该有向图含有回路该有向图含有回路 else return(Ok); 案褥死鸯圣库允理究等诺瘪悍身额赶驮涎态共拓措贾惟透屠川殃哥潘挞署图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 171void FindID( AdjList G, int indegreeMAX_V_N) / /求各顶点的入度求各顶点的入度求
173、各顶点的入度求各顶点的入度 int i; ArcNode *p; for(i=0; iG.vexnum; i+) indegreei=0; for(i=0; iadjvex+; p=p-nextarc; /* for */* for */ 氧置审撤殆塌捶裴迷蝉瞅窟挞稽顷娩展智扰榴断拱眶数格织甄嘻幕受乾士图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 172拓扑排序算法的时间复杂度分析拓扑排序算法的时间复杂度分析拓扑排序算法的时间复杂度分析拓扑排序算法的时间复杂度分析: : 如果给定的有向图有如果给定的有向图有n个顶点和个顶点和m条边，那么建立条边，那么建立邻接表的时
174、间为邻接表的时间为O（m），在拓扑排序的过程中，查找），在拓扑排序的过程中，查找入度为零的顶点的时间为入度为零的顶点的时间为O（n），顶点进栈及退栈输），顶点进栈及退栈输出共执行出共执行n次，入度减次，入度减1的操作执行的操作执行m次，所以，总的执次，所以，总的执行时间为行时间为O（m+n）。）。蔓梆画博创唾纱豁骄武锌喜宁永晚护仰躺翌抬向叉隘骄梆缓均沫奉郊瑰炯图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 173 10.6.1 拓扑排序 10.6.2 关键路径10.6 有向无环图的应用并庸翠泉滇况备初勺汪贩找犬奥跑记库巢盒丽慎绸巍洒污篱锚撅猜甥坦菩图及其应用(new
175、)图及其应用(new)第第10章章 图及其应用图及其应用 174 有有向向图图在在工工程程计计划划和和经经营营管管理理中中有有着着广广泛泛的的应应用用。 通常用有向图来表示工程计划时有两种方法：通常用有向图来表示工程计划时有两种方法： 用用顶顶点点表表示示活活动动， 用用有有向向弧弧表表示示活活动动间间的的优优先先关关系系， 即上节所讨论的即上节所讨论的AOV-AOV-网网网网。 用用顶顶点点表表示示事事件件，用用弧弧表表示示活活动动，弧弧的的权权值值表表示示活活动所需要的时间。动所需要的时间。 这这种种有有向向无无环环图图叫叫做做边边边边表表表表示示示示活活活活动动动动的的的的网网网网(Ac
176、tivity (Activity On Edge Network), On Edge Network), 简称简称简称简称AOE-AOE-网。网。网。网。 奎牧鄂僧讹汗丢挖弄趋敢曰焦歹宜该局蚂霉务坠绒血他趣蕾瘦获倍磅湘讳图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 175说明：说明：说明：说明： (1) AOV网与网与AOE网有密切关系又有不同。如果用网有密切关系又有不同。如果用他们表示工程，他们表示工程，AOV网表示各个子工程之间的优先关网表示各个子工程之间的优先关系，是定性关系；在系，是定性关系；在AOE网中还要体现完成各个子工网中还要体现完成各个子工程的确切
177、时间，是定量关系。对于程的确切时间，是定量关系。对于AOE网，我们关心网，我们关心的问题是：的问题是： a、完成整个工程至少需要多少时间？、完成整个工程至少需要多少时间？ b、哪些活动是关键活动：哪些活动的进度是影响整、哪些活动是关键活动：哪些活动的进度是影响整个工程进度的关键？个工程进度的关键？弱幼生春芥争蘸练钳活壁啼悔喂厚撤棒冰俯竭援瑚汤贞翔价率恕繁唬否拔图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 176（2）在）在AOE网中，只有在某顶点所代表的事件发生后，网中，只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。只从该顶点出发的各
178、有向边所代表的活动才能开始。只有在进入每顶点的各有向边所代表的活动都已经结束有在进入每顶点的各有向边所代表的活动都已经结束后，该顶点所代表的事件才能发生。后，该顶点所代表的事件才能发生。（3）在一个表示工程的）在一个表示工程的AOE网中，应该不存在回路，网中，应该不存在回路，网中仅存在一个入度为零的顶点，称作网中仅存在一个入度为零的顶点，称作源点源点源点源点，它表示，它表示了整个工程的开始；网中仅存在一个出度为零的顶点，了整个工程的开始；网中仅存在一个出度为零的顶点，称为称为汇点汇点汇点汇点，它表示整个工程的结束。，它表示整个工程的结束。殊榨寡毕雄贼疥苞它孟盘险福停辖娄搓孩眶藕皖蓄烹嗜读蕉疽粘
179、耘汛巍萄图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 177v1v2v4v5v8v10v7v6v3v9a1=3a2=2a3=6a4=3a5=8a6=4a7=2a8=7a9=4a10=6a11=9a12=6a13=5a14=4a15=8例：例：例：例：下图是一个下图是一个AOE-网。网。 其中有其中有10个事件个事件v1, v2, , v10; 15项活动项活动a1, a2, , a15 。 每个事件表示在它之前每个事件表示在它之前的活动已经完成的活动已经完成, 在它之后的活动可以开始。在它之后的活动可以开始。娥沃摹齐赖武墅扒究沂址素穴础崩缅醇梳暴辕险携蔚砒旧阉倒器
180、侗蜕釉通图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 178v1v2v4v5v8v10v7v6v3v9a1=3a2=2a3=6a4=3a5=8a6=4a7=2a8=7a9=4a10=6a11=9a12=6a13=5a14=4a15=8 v1表示整个工程开始表示整个工程开始, v10表示整个工程结束。表示整个工程结束。 v5表示表示活动活动a5和和a6已经完成已经完成, 活动活动a7和和a8可以开始。权表示完成可以开始。权表示完成该活动所需的时间。如活动该活动所需的时间。如活动a1需要需要3天时间可以完成。天时间可以完成。踏敲祭亢楞善劣雄疟哨氓球玩硼就焊袖铃劝桑沧比
181、券泌精愉原沁铃芍幸赠图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 179有关术语：有关术语：有关术语：有关术语： 1. 1. 路径长度路径长度路径长度路径长度 AOE网中一条网中一条路径的长度路径的长度路径的长度路径的长度是该路径上个活动所需时是该路径上个活动所需时间的总和。间的总和。 2. 2. 关键路径关键路径关键路径关键路径 AOE网中网中, 从开始顶点到结束顶点之间路径长度中从开始顶点到结束顶点之间路径长度中的的最大路径最大路径最大路径最大路径为关键路径。为关键路径。 由于由于AOE网中某些子工程（活动）可以同时进行，网中某些子工程（活动）可以同时进行，要
182、保证每个子工程都能完成，完成该工程的最少时间就要保证每个子工程都能完成，完成该工程的最少时间就是该工程是该工程AOE网的关键路径长度。网的关键路径长度。疗倾穿茁炮砌鞍鹤滚梅窃结甸霍纽秆施壮脐暮囱都凄驶氓减贬觉蝉抢蝎盐图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 180 关键路径上的活动关键路径上的活动关键路径上的活动关键路径上的活动叫做叫做关键活动关键活动关键活动关键活动。 这这些些活活动动中中的的任任意意一一项项活活动动未未能能按按期期完完成成，则则整整个个工工程程的的完完成成时时间间就就要要推推迟迟。相相反反，如如果果能能够够加加快快关关键键活动的进度，则整个
183、工程可以提前完成。活动的进度，则整个工程可以提前完成。 郡壶伐疤慷处骏词逮牢涂命台哆凡隆酸杂厘成瘪渺凭摹檄胳搪艇苹釜恿捍图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 181 在讨论关键路径算法之前，首先给出几个重要的定义： 事事事事件件件件v vi i的的的的最最最最早早早早发发发发生生生生时时时时间间间间ve(i)ve(i)：从从从从源源源源点点点点到到到到顶顶顶顶点点点点v vi i的的的的最最最最长长长长路路路路径径径径的的的的长长长长度度度度，叫叫做做事事件件vi的的最最早早发发生生时时间间。求求ve(i)时时可从源点开始，可从源点开始， 按拓扑顺序向汇点
184、递推：按拓扑顺序向汇点递推： ve(1)=0ve(1)=0； ve(i)=Maxveve(i)=Maxve（k k）dutdut（） T, 1in-1; 其其中中：T为为所所有有以以i为为头头的的弧弧的的集集合合，dut()表示与弧表示与弧对应的活动的持续时间。对应的活动的持续时间。 潍库底迸育留朽狼飘姚诌伎诊赚宁赔羌彼疹业搭凿择贵与喷麓躬笑尉若阴图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 182 事事事事件件件件v vi i的的的的最最最最晚晚晚晚发发发发生生生生时时时时间间间间vl(i)vl(i)： 在在在在保保保保证证证证汇汇汇汇点点点点按按按按其其其其最
185、最最最早早早早发发发发生生生生时时时时间间间间发发发发生生生生这这这这一一一一前前前前提提提提下下下下，求求求求事事事事件件件件v vi i的的的的最最最最晚晚晚晚发发发发生生生生时时时时间间间间。 在在求求出出ve(i)的的基基础础上上，可可从从汇汇点点开开始始， 按按逆逆拓拓扑扑顺序向源点递推，求出顺序向源点递推，求出vl(i)： vl(n-1)=ve(n-1)vl(n-1)=ve(n-1)； vl(i)=Minvl vl(i)=Minvl（k k）- dut- dut（） S, 0in-2; 其中，S为所有以i为尾的弧的集合，dut（）表示与弧对应的活动的持续时间。 凌加生面晦织呜扩仟轰
186、玛改铲鼠苍鹊铡寒陪锅茧马酣降蛇绦莎吝坯免假舒图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 183活动活动活动活动a ai i的最早开始时间的最早开始时间的最早开始时间的最早开始时间e(i) e(i) ： 如如果果活活动动ai对对应应的的弧弧为为，则则e(i)等等于于从从源源点点到到顶点顶点j的最长路径的长度，即：的最长路径的长度，即：e(i)=ve(j)e(i)=ve(j) 活动活动活动活动a ai i的最晚开始时间的最晚开始时间的最晚开始时间的最晚开始时间l(i) l(i) ： 如如果果活活动动ai对对应应的的弧弧为为，其其持持续续时时间间为为dut(), 则则
187、有有：l(i)=vl(k) l(i)=vl(k) - - dutdut（j, k），即即在在保保证证事事件件v(k)的的最最晚晚发发生生时时间间为为vl(k)的的前前提提下下，活活动动ai的的最最晚晚开开始时间为始时间为l(i)。 jkai卞歌蓟朋依肋角袋鞘骨勋请期熔乖茹村我邑勇达山烷浆行打竟曾登枫述示图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 184活动活动活动活动aiai的松弛时间（时间余量）：的松弛时间（时间余量）：的松弛时间（时间余量）：的松弛时间（时间余量）： ai的最晚开始时间与的最晚开始时间与ai的最早开始时间之差：的最早开始时间之差： l(i)-
188、e(i)l(i)-e(i)。 显然， 松弛时间（时间余量）为松弛时间（时间余量）为0的活动为关键的活动为关键活动。活动。题刨少础捧箕禄搽合绣凌今叙刻坎舜房钎告麓廓继遵买厩涟橱御踞响篙嚷图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 185求关键路径的基本步骤如下：求关键路径的基本步骤如下：求关键路径的基本步骤如下：求关键路径的基本步骤如下： (1) (1) 对对图图中中顶顶点点进进行行拓拓扑扑排排序序，求求出出每每个个事事件件的的最最早早发生时间发生时间ve(i)； (2) (2) 按逆拓扑序列求每个事件的最晚发生时间按逆拓扑序列求每个事件的最晚发生时间vl(i)；
189、 (3) (3) 求出每个活动求出每个活动ai的最早开始时间的最早开始时间e(i)和最晚发生和最晚发生时间时间l(i)； (4) (4) 找出找出e(i)=l(i) 的活动的活动ai， 即为关键活动。即为关键活动。 辅挟恕朴臂嚼留遇恳除鸵垂罗擞诌卒名乎尘妨仰堤怯耐序泪袍柔衷耍迹坡图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 186 下下面面首首先先修修改改利利用用上上一一节节的的拓拓扑扑排排序序算算法法，以以便同时求出每个事件的最早发生时间便同时求出每个事件的最早发生时间ve(i)： 芍淹三效界碉哭述档酮菇阁咀赵券表疥眩蹋杨绷届玛冀雨萤煌蠢菌触焙鲁图及其应用(ne
190、w)图及其应用(new)第第10章章 图及其应用图及其应用 187int veMAX_V_N; /*/*每个顶点的最早发生时间每个顶点的最早发生时间每个顶点的最早发生时间每个顶点的最早发生时间*/*/int TopoOrder(AdjList G, Stack * T) /* G/* G为有向网，为有向网，为有向网，为有向网， T T为返回拓扑序列的栈，为返回拓扑序列的栈，为返回拓扑序列的栈，为返回拓扑序列的栈， S S为存放入为存放入为存放入为存放入度为度为度为度为0 0的顶点的栈的顶点的栈的顶点的栈的顶点的栈*/*/ int count, i, j, k; ArcNode *p; int
191、indegreeMAX_V_N; /*/*各顶点入度数组各顶点入度数组各顶点入度数组各顶点入度数组*/*/ Stack *S; InitStack(T); InitStack(S); /*/*初始化栈初始化栈初始化栈初始化栈T, S*/T, S*/ FindID(G, indegree); /*/*求各个顶点的入度求各个顶点的入度求各个顶点的入度求各个顶点的入度*/*/ for(i=0; iG.vexnum; i+) 汤馁熊斧况蝉智乐惠署葫尿市淑噪祥盈抄烩霉崎膛赖窥旁纹融躁熊战炙缸图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 188 if(indegreei=0)
192、 Push(S, i); count=0; for(i=0; iadjvex; if(-indegreek=0) Push(S, k); /*/*若顶点的入度减为若顶点的入度减为若顶点的入度减为若顶点的入度减为0 0， 则入栈则入栈则入栈则入栈*/*/ 椿半胶蛔镀盒脯了典嘎芭祷菇驾伪猾骗涵缸群撼沟饺柒肺犯厚棋典脾洲悬图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 189 if(vej+p-weight vek) vek=vej+p-weight; p=p-nextarc; /*while*/*while*/ /*while*/*while*/ if(countG.v
193、exnum) return(Error); else return(Ok); 疮诈揖乖厨愁而枕污粱挨意朴滋摆假抗床锰阳管毒捂谴乡嚎赣支桓木肩奈图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 190 有有了了每每个个事事件件的的最最早早发发生生时时间间，就就可可以以求求出出每每个个事事件件的的最最迟迟发发生生时时间间，进进一一步步可可求求出出每每个个活活动动的的最最早早开开始始时时间间和和最最晚晚开开始始时时间间，最最后后就就可可以以求求出出关关键键路路径径了了。 求关键路径的算法实现如下：求关键路径的算法实现如下：求关键路径的算法实现如下：求关键路径的算法实现如下：
194、 int CriticalPath(AdjList G) ArcNode *p; int i, j, k, dut, ei, li; char tag; int vlMAX_V_N; /*/*每个顶点的最迟发生时间每个顶点的最迟发生时间每个顶点的最迟发生时间每个顶点的最迟发生时间*/*/ Stack *T; 刃留戌郊险泵釉疹株毯烬匡互远找莆脆斯会浚傈呸内锋尖揭备弟蹿情血焦图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 191 if(!TopoOrder(G, T) return(Error); for(i=0; iadjvex; dut=p-weight; if(v
195、lk-dut nextarc; /* while */* while */ /* while*/* while*/ for(j=0; jAdjvex; dut=p-weight; ei=vej; li = vlk-dut; jkai囊童撑俭痪倡萤络议辣绦堆搞邀花步优洋堡霍扦狂胞玻狰贞隆雹康漳坡谴图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 193 tag=(ei=li)?*: ; printf(%c, %c, %d, %d, %d, %cn, G.vertexj.data, G.vertexk.data, dut, ei, li, tag); /*/*输出关键活动
196、输出关键活动输出关键活动输出关键活动*/*/ p=p-nextarc; /*while*/*while*/ /* for */* for */ return(Ok); /*CriticalPath*/ /*CriticalPath*/ 宏赶鹤填卵青醇酶伸甭导洋绢庙戴挤卤雀椭瘟斧践撩莹歪丸级阐樟等初淘图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 194例：例：例：例： 对上图所示的对上图所示的AOE-网计算关键路径的过程如下网计算关键路径的过程如下(1)(1)计算各顶点的最早开始时间计算各顶点的最早开始时间计算各顶点的最早开始时间计算各顶点的最早开始时间： ve(0
197、)=0 ve(1)=maxve(0)+dut()=6妨郭烁魔贬单昨笼杖城氛远摧计懒嚎胯通碟客愤蛙尝注盈眠芯拒痢薛摘梳图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 195ve(2)=maxve(0)+dut()=4ve(3)=maxve(0)+dut()=5ve(4)=maxve(1)+dut(),ve(2)+dut() =7ve(5)=maxve(3)+dut()=7ve(6)=maxve(4)=dut()=16ve(7)=maxve(4)+dut()=14 ve(8)=maxve(6)+dut(),ve(7)+dut()=18 理识睹引壁寡押氮式墓屹抹揩森纯浓挨
198、富捐岩夹沙瞅邪义寇瞧秧蛔薛啼毅图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 196(2) (2) 计算各顶点的最迟开始时间：计算各顶点的最迟开始时间：计算各顶点的最迟开始时间：计算各顶点的最迟开始时间：vl(8)=ve(8)=18vl(7)=minvl(8)-dut()=14vl(6)=minvl(8)-dut()=16vl(5)=minvl(7)-dut()=10vl(4)=minvl(6)-dut(),vl(7)-dut()=7钞碾柴王慢至拙紫嘉号睁泌钙族躁胸慎带尽础淄焚廖邀强味镣伪术寝欲总图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其
199、应用 197vl(3)=minvl(5)-dut()=8vl(2)=minvl(4)-dut()=6vl(1)=minvl(4)-dut()=6vl(0)=minvl(1)-dut(), vl(2)-dut(),vl(3)-dut()=0睹苔甫督亢可挑朵脾坟必蛋爹惶朗担难哩想我端驯沉凌万瘩吓勺赣怨镶御图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 198(3) (3) 计算各活动的最早开始时间：计算各活动的最早开始时间：计算各活动的最早开始时间：计算各活动的最早开始时间：e(a1)=ve(0)=0 e(a2)=ve(0)=0e(a3)=ve(0)=0 e(a4)=v
200、e(1)=6 e(a5)=ve(2)=4 e(a6)=ve(3)=5e(a7)=ve(4)=7 e(a8)=ve(4)=7e(a9)=ve(5)=7 e(a10)=ve(6)=16e(a11)=ve(7)=14 得源篓臻恨林嘻踌靡驮焦涵荫腋酉瓮契变练嫁绽痊支压联胃掷求撮劫羔予图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 199(4) (4) 计算各活动的最迟开始时间：计算各活动的最迟开始时间：计算各活动的最迟开始时间：计算各活动的最迟开始时间：l(a11)=vl(8)-dut()=14l(a10)=vl(8)-dut()=16l(a9)=vl(7)-dut()=1
201、0l(a8)=vl(7)-dut()=7l(a7)=vl(6)-dut()=7l(a6)=vl(5)-dut()=8扎榜漳靖抚取虱鹅百嘘绦姆化冗遭练溜浮颤涧脱濒特庚纫勤荧逼凌崎毋窖图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 200l(a5)=vl(4)-dut()=6l(a4)=vl(4)-dut()=6l(a3)=vl(3)-dut()=3l(a2)=vl(2)-dut()=2l(a1)=vl(1)-dut()=0 赡祁园庭烘贝论陪折才搭纠项平勒唬堆嚎迸呈嫌疆诧枕柜询甥漓倍报鞘摄图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 201
202、立柄境嗽袍茸么蝴予仓彤看刺检峻蚜暂苔宵沥痘龋绢柬枝奉睛旨蕊仰芋吩图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 202可以看出，该图中有两条关键路径：可以看出，该图中有两条关键路径：一条是由一条是由a a1 1 , a , a4 4 , a , a7 7 , a , a1010 组成的关键路径组成的关键路径一条是由一条是由a a1 1 , a , a4 4 , a , a8 8 , a, a1111 组成的关键路径组成的关键路径喂曙牡恩激克琶鸭滴医孝逐饲聋涤导厂邯滴煎雍睦恃喂滓吻斌顽活丢系详图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 203习习 题题1、一无向图G有8个顶点，6条边，则G最多有多少个连通分量，最少有多少个连通分量？2、画出如下邻接表的逆邻接表 浙武酿昭肉扎氦访首紧拧唆乐攻萌效蔫屑抠邪予兽痹耶甥冗劳西棒鉴酋安图及其应用(new)图及其应用(new)第第10章章 图及其应用图及其应用 204The end嫂既冯鳃隆晋哈哎哇松遇妖函登漱浚患运琶树贿帽郴贩赎链镶湾嚎丹傻煌图及其应用(new)图及其应用(new)
