数据结构第三讲

《数据结构第三讲》由会员分享，可在线阅读，更多相关《数据结构第三讲（89页珍藏版）》请在金锄头文库上搜索。

1、觅莫从扳探雨溜厌构舔帮楔延酪格剑床貉罐随怎蚀饲窑督完懒妮鲜赫聪抿数据结构第三讲数据结构第三讲第三讲 图尽梢案键翁咙旭曳环焉镣涸毖江臼座澳雨郴喘墓骄托申戮斤昆挣酮梦圆冉数据结构第三讲数据结构第三讲1 1本章出题特点本章出题特点 在历年统考里在历年统考里,大多以客观题不劳形式出大多以客观题不劳形式出现现,具体如下具体如下:年份年份客观客观主观主观20091(2分分)1(10分分)20102(4分分)20111(2分分)1(8分分)20124(8分分)率稚吱怠碘园碟性釉衰疮汽窿炳馅缚嗓壹懦心犊体撮坞圾悄闹肪摇作碑秆数据结构第三讲数据结构第三讲2知识点归纳图图应用应用遍历方式遍历方式存储结构存储结构关

2、键路径关键路径最小生成树最小生成树广度优先广度优先深度优先深度优先邻接表邻接表最短路径最短路径拓扑排序拓扑排序邻接矩阵邻接矩阵基本概念基本概念了解了解掌握掌握掌握掌握掌握、应用掌握、应用基本概念基本概念逐使强磷讫宅汾咳逝决凑辱粟挽楷缮狸桂唾琉爷甘滥掳拆渝抵吻滚屈擒匪数据结构第三讲数据结构第三讲3一、图的概念和相关术语一、图的概念和相关术语图的定义图的定义 图图(Graph)G由由两两个个集集合合V(Vertex)和和E(Edge)组组成成,记记为为G=(V,E),其其中中V是是顶顶点点的的有有限限集集合合,记记为为V(G),E是是连连接接V中中两两个个不不同同顶顶点点(顶顶点点对对)的的边边的

3、的有有限限集集合合,记记为为E(G)。 顶点集合为空的图称为空图。顶点集合为空的图称为空图。 E(G)为空时为空时,图中只有顶点而没有边。图中只有顶点而没有边。狙唐坑帅招阐颈窘抵驮辊火鳖蕊巴憾骤臭帅涎额羡碾拨呕癣虞杆格菊震蓖数据结构第三讲数据结构第三讲4图的基本术语图的基本术语 1. 端点和邻接点端点和邻接点 在在一一个个无无向向图图中中,若若存存在在一一条条边边(vi,vj),则则称称vi和和vj为为此此边边的的两两个个端端点点,并称它们互为并称它们互为邻接点邻接点。 在在一一个个有有向向图图中中,若若存存在在一一条条边边,则则称称此此边边是是顶顶点点vi的的一一条条出出边边,同同时时也也是

4、是顶顶点点vj的的一一条条入入边边；称称vi和和vj分分别别为为此此边边的的起起始始端端点点(简简称称为为起起点点)和和终终止止端端点点(简简称称终终点点)；称称vi和和vj互互为为邻接点邻接点。13024(a)13024(b)叛炳轻戴剥役崭龟两氯厨咋帧涝抹府存戏萎衍勋祟脑颧擒宋衙召泣必徽历数据结构第三讲数据结构第三讲52. 路径和路径长度路径和路径长度 在在一一个个图图G=(V,E)中中,从从顶顶点点vi到到顶顶点点 vj的的 一一 条条 路路 径径 是是 一一 个个 顶顶 点点 序序 列列(vi,vi1,vi2,vim,vj),若若此此图图G是是无无向向图图,则则边边(vi,vi1),(v

5、i1,vi2),(vim-1,vim),(vim,vj)属属于于E(G)；若若此此图图是是有有向向图图,则则,属于属于E(G)。 路路径径长长度度是是指指一一条条路路径径上上经经过过的的边边的的数数目目。若若一一条条路路径径上上除除开开始始点点和和结结束束点点可可以以相相同同外外,其其余余顶顶点点均均不不相相同同,则则称称此此路路径径为为简简单单路路径径。例例如如,有有图图中中,(v0,v2,v1)就就是是一一条条简简单单路路径径,其其长长度度为为2。2103襄拇隆敖吗屈宫湃坷蒸垮肩谐熟捶净替标逼蓉扰褒消臼邻幅纫痞黎拦酱范数据结构第三讲数据结构第三讲6 3. 连通、连通图和连通分量连通、连通图

6、和连通分量 在在无无向向图图G中中,若若从从顶顶点点vi到到顶顶点点vj有有路路径径,则则称称vi和和vj是是连通连通的。的。 若若图图G中中任任意意两两个个顶顶点点都都连连通通,则则称称G为为连连通通图图,否否则则称称为为非连通图非连通图。 无无向向图图G中中的的极极大大连连通通子子图图称称为为G的的连连通通分分量量。显显然然,任任何何连连通通图图的的连连通通分分量量只只有有一一个个,即即本本身身,而而非非连连通通图图有有多多个个连连通分量。通分量。1023102(b)(a)3“极大极大”的含义：指的是的含义：指的是对子图再增加图对子图再增加图G中的其它中的其它顶点，子图就不再连通。顶点，子

7、图就不再连通。靳芥颐匀音朔验诺钢玲鉴争颈刃蛊拐贤管巴内僵誊距焰试泰哮亚芭锯稳匪数据结构第三讲数据结构第三讲7 4. 顶点的度、入度和出度顶点的度、入度和出度 在在无无向向图图中中,顶顶点点所所具具有有的的边边的的数数目称为该目称为该顶点的度顶点的度。 在在有有向向图图中中,以以顶顶点点vi为为终终点点的的入入边边的的数数目目,称称为为该该顶顶点点的的入入度度。以以顶顶点点vi为为始始点点的的出出边边的的数数目目,称称为为该该顶顶点点的的出出度度。一一个个顶顶点点的的入入度度与与出出度度的的和和为为该该顶顶点点的的度。度。 若若一一个个图图中中有有n个个顶顶点点和和e条条边边,每每个顶点的度为个

8、顶点的度为di(1in),则有：则有：13024(a)13024(b)媒盒抽魁吐湖炭逐讯鞠鼻什俘竞傲喝逢梦笋巨沟腹褐僵险廓雁法扫缉廓酌数据结构第三讲数据结构第三讲8 5. 完全图完全图 若无向图中的每两个顶点之间都若无向图中的每两个顶点之间都存在着一条边存在着一条边,有向图中的每两个顶点有向图中的每两个顶点之间都存在着方向相反的两条边之间都存在着方向相反的两条边,则称则称此图为此图为完全图完全图。 显然显然,完全无向图包含有完全无向图包含有n(n-1)/2条条边边,完全有向图包含有完全有向图包含有n(n-1)条边。条边。 例如例如,图图(a)所示的图是一个具有所示的图是一个具有4个顶点的完全无

9、向图个顶点的完全无向图,共有共有6条边。图条边。图(b)所示的图是一个具有所示的图是一个具有4个顶点的完个顶点的完全有向图全有向图,共有共有12条边。条边。 (b)10231023(a)仇哮淹谍忆侯非再珊檬园窍侨役藕涵诡啡锨嚎朗公旅拥朵连稍瞒航角纫仑数据结构第三讲数据结构第三讲9 6. 子图子图 设设 有有 两两 个个 图图 G=(V,E)和和G=(V,E),若若 V是是 V的的 子子 集集 ,即即V V,且且E是是E的的子子集集,即即E E,则则称称G是是G的的子子图图。例例如如图图(b)是是图图(a)的的子子图图,而而图图(c)不不是是图图(b)的的子子图。图。(a)1302413024(

10、b)13024(c)芦饶瓜蟹隘拔仗倍跑蚂循尼焦段柴条宗世涡综哟赐宁诅含育草卫洒丙搅矾数据结构第三讲数据结构第三讲10 7. 回路或环回路或环 若若一一条条路路径径上上的的开开始始点点与与结结束束点点为为同同一一个个顶顶点点,则则此此路路径径被被称称为为回回路路或或环环。开开始始点点与与结结束束点点相相同同的的简简单单路路径被称为径被称为简单回路简单回路或或简单环简单环。 例例如如,右右图图中中,(v0,v2,v1,v0)就就是一条简单回路是一条简单回路,其长度为其长度为3。1023连煤秀拢伸咱埃堵幻郭揍牙涌宛茫颊苞逼勉籽蜀焦彤甲梧他捶峰话课鬃袍数据结构第三讲数据结构第三讲11 8. 强连通图和

11、强连通分量强连通图和强连通分量 在有向图在有向图G中中,若从顶点若从顶点vi到到顶点顶点vj有路径有路径,则称从则称从vi到到vj是是连连通通的。的。 若图若图G中的任意两个顶点中的任意两个顶点vi和和vj都连通都连通,即从即从vi到到vj和从和从vj到到vi都都存在路径存在路径,则称图则称图G是是强连通图强连通图。例如例如,右边两个图都是强连通图。右边两个图都是强连通图。 有向图有向图G中的中的极大极大强连通子强连通子图称为图称为G的的强连通分量强连通分量。显然。显然,强强连通图只有一个强连通分量连通图只有一个强连通分量,即本即本身身,非强连通图有多个强连通分量。非强连通图有多个强连通分量。

12、1023102(b)(a)寐圈拌抑苦滑孔晴爱稠铰灵谓纯枷匹间吓殴啤鞋粕枝戒栖蔑沛滑灶烩捎辊数据结构第三讲数据结构第三讲12 例例 有有n个顶点的有向强连通图最多需要多少条边？最个顶点的有向强连通图最多需要多少条边？最少需要多少需要多 少条边？少条边？ 答：有答：有n个顶点的个顶点的有向强连通图有向强连通图最多有最多有n(n-1)条边条边(构成一个有向完全图的情况构成一个有向完全图的情况)；最少有；最少有n条边条边(n个顶个顶点依次首尾相接构成一个环的情况点依次首尾相接构成一个环的情况)。 炊羞洗哥屁暗稀袖制吾板闹吝裸煮竞余兼灌月厘菏挺仅爸透握优谈脯托镶数据结构第三讲数据结构第三讲13练习题：

13、若一个非连通无向图有10条 边，请问，该图至少有多少 个顶点？答：要保证图非连通，则至少需要两个连通分量，可让一个分量里只有一个顶点，另一个分量为一个完全图。5个顶点的无向完全图共有10个顶点，所以至少需要6个顶点。狭锦撅诗炬坚江卑捌期咨痴撰武犹载扫蛆唬回丰楔搀邯职诬沾死洪苑缠隔数据结构第三讲数据结构第三讲14真题演练真题演练（1）若无向图）若无向图G=（V，E）中含有）中含有7个顶点，个顶点，要保证要保证G在在任何情况下任何情况下都是连通的，则需要都是连通的，则需要的边数最少为的边数最少为 （ ） A、6 B、15 C、16 D、21（2）一个无向图有）一个无向图有16条边，若度为条边，若度

14、为4的顶点的顶点有有3个，度为个，度为4的顶点有的顶点有3个，其余顶点的度个，其余顶点的度数均小于数均小于3，则该图至少有（，则该图至少有（ ）个顶点。）个顶点。 A、10 B、11 C、12 D、13诡字程权戏壳催蕉握绘筛娇跑暑硕蔷峡库刑吱舒罐喉秸沫夏凭瑶绵菜想吭数据结构第三讲数据结构第三讲15二、图的存储结构二、图的存储结构邻接矩阵存储方法邻接矩阵存储方法 邻邻接接矩矩阵阵是是表表示示顶顶点点之之间间相相邻邻关关系系的的矩矩阵阵。设设G=(V,E)是是具具有有n(n0)个个顶顶点点的的图图,顶顶点点的的顺顺序序依依次次为为(v0,v1,vn-1),则则G的的邻邻接接矩矩阵阵A是是n阶阶方方

15、阵阵,其其定定义义如如下：下： (1) 如果如果G是无向图是无向图,则：则： Aij= 1:若若(vi,vj)E(G) 0:其他其他 (2) 如果如果G是有向图是有向图,则：则： Aij= 1:若若E(G) 0:其他其他骚申惠辆浅蝉扁蹭滑颊链吞门腑恳或距安分后掏厦棍株壤多蔑词桨霍澜驭数据结构第三讲数据结构第三讲16彦补农育待谰散矛堰湾袒嗜婪诵搐墓瞒毫选企宏您厦谭魂科废吩曹医琅舀数据结构第三讲数据结构第三讲17(3) 如果如果G是带权无向图是带权无向图,则：则： Aij= wij :若若vivj且且(vi,vj)E(G) :其他其他(a) 带权无向图带权无向图 354126abcde3(b) 邻

16、接矩阵邻接矩阵 6 2 6 3 4 32 3 1 4 3 5 3 5 掳唁萎火打馒毋桑潘估涩颤豌撼蹈卖陨蜜凝颅迷痪惫厦帮晰堆亮丑爪营恬数据结构第三讲数据结构第三讲18(b) 邻接矩阵邻接矩阵 6 2 3 3 1 4 4 5 (a) 带权有向图带权有向图 354126abcde3(4) 如果如果G是带权有向图是带权有向图,则：则： Aij= wij :若若vivj且且E(G) :其他其他恐翱浮恼砖血戌胀增肪醚推桩泡扒浩咽酝禾二匠抓世睦昭迭耘爵奄涧民浦数据结构第三讲数据结构第三讲19思考题：思考题：对于有对于有n个顶点个顶点e条边的无向图，邻接矩阵表示时有多少条边的无向图，邻接矩阵表示时有多少个元

17、素，多少个非个元素，多少个非0元素？元素？对于有对于有n个顶点个顶点e条边的有向图，邻接矩阵表示时有多少条边的有向图，邻接矩阵表示时有多少个元素，多少个非个元素，多少个非0元素？元素？阉号烟柑纬缀培瓦沙讼夯盟长赊旦奶汕傅抄奈秽镐困蒋舆粱鼎恢朱茧姓竭数据结构第三讲数据结构第三讲20邻接矩阵的特点如下：邻接矩阵的特点如下： (1) 图的邻接矩阵表示是图的邻接矩阵表示是唯一唯一的。的。 (2) 无无向向图图的的邻邻接接矩矩阵阵一一定定是是一一个个对对称称矩矩阵阵。因因此此,按按照照压压缩缩存存储储的的思思想想,在在具具体体存存放放邻邻接接矩矩阵阵时时只只需需存存放放上上(或或下下)三角形阵的元素即可

18、。三角形阵的元素即可。 (3) 不不带带权权的的有有向向图图的的邻邻接接矩矩阵阵一一般般来来说说是是一一个个稀稀疏疏矩矩阵阵,因因此此,当当图图的的顶顶点点较较多多时时,可可以以采采用用三三元元组组表表的的方方法法存存储储邻接矩阵。邻接矩阵。 (4) 对对于于无无向向图图,邻邻接接矩矩阵阵的的第第i行行(或或第第i列列)非非零零元元素素(或或非非元素元素)的个数正好是第的个数正好是第i个顶点个顶点vi的度。的度。艘森滦窍舜坟查病宋翁识钾摧汉雁舒秸斌恋嗣铲曲毅牟谓蠢向笆甫帮咕庶数据结构第三讲数据结构第三讲21 (5) 对对于于有有向向图图,邻邻接接矩矩阵阵的的第第i行行(或或第第i列列)非非零零

19、元元素素(或或非非元素元素)的个数正好是第的个数正好是第i个顶点个顶点vi的出度的出度(或入度或入度)。 (6) 用用邻邻接接矩矩阵阵方方法法存存储储图图,很很容容易易确确定定图图中中任任意意两两个个顶顶点点之之间间是是否否有有边边相相连连。但但是是,要要确确定定图图中中有有多多少少条条边边,则则必必须须按按行行、按按列列对对每每个个元元素素进进行行检检测测,所所花花费费的的时时间间代代价价很很大大。这这是用邻接矩阵存储图的局限性。是用邻接矩阵存储图的局限性。潘剐桶莆衅裤陕糖掸难瓤胀咆誓佛佃痕狼隆伦哇排媒序节吮席镜拈之牟畸数据结构第三讲数据结构第三讲228.2.2 邻接表存储方法邻接表存储方法

20、 图图的的邻邻接接表表存存储储方方法法是是一一种种顺顺序序分分配配与与链链式式分分配配相相结结合合的的存存储储方方法法。在在邻邻接接表表中中,对对图图中中每每个个顶顶点点建建立立一一个个单单链链表表,第第i个个单单链链表表中中的的结结点点表表示示依依附附于于顶顶点点vi的的边边(对对有有向向图图是以顶点是以顶点vi为尾的弧为尾的弧)。每个单链表上附设一个表头结点。每个单链表上附设一个表头结点。卉痢战窄腮晓险追想弊碟脂翰葬苯吃阶答异裕收起久历毋俱碘锌士顽拦尘数据结构第三讲数据结构第三讲23 其中其中,表结点由三个域组成表结点由三个域组成,adjvex指示与顶点指示与顶点vi邻接的点在图中的位置邻

21、接的点在图中的位置,nextarc指示下一条边或弧的指示下一条边或弧的结点结点,info存储与边或弧相关的信息存储与边或弧相关的信息,如权值等。如权值等。 表头结点由两个域组成表头结点由两个域组成,data存储顶点存储顶点vi的名称或的名称或其他信息其他信息,firstarc指向链表中第一个结点。指向链表中第一个结点。 advexnextarcinfodatafirstarc表头节点表节点叶实廉奎尧载阔王晰岳彰儡坞芬舶绕路篆檀嫩寂熏系栽丘咨界拘孝罗烛糟数据结构第三讲数据结构第三讲24014 MAX_VEX-12 02 2 01234v1v2 v3 v4 v5 3 04 (b) 逆邻接表逆邻接表

22、(a) 有向图有向图v1v2v3v4v5MAX_VEX-113 2 3 01234(a) 正邻接表正邻接表v1v2 v3 v4 v5 戎财曝联更畦丁抓拈硼擦澎刃袖麻瞬热涟椭自箩殆佃菜婪狄拯呕焙膝箱伤数据结构第三讲数据结构第三讲25思考题：思考题：对于有对于有n个顶点个顶点e条边的无向图，邻接表表示时条边的无向图，邻接表表示时有多少个表头结点，多少个表结点？有多少个表头结点，多少个表结点？对于有对于有n个顶点个顶点e条边的有向图，邻接表表示时条边的有向图，邻接表表示时有多少个表头结点，多少个表结点？有多少个表头结点，多少个表结点？垦窗第分良罢呕以臆斩钒蹭椅尖宛仕铆凸磋傈嗜唉晚钟饿峡葬亩屡晦晃胸数

23、据结构第三讲数据结构第三讲26邻接表的特点如下：邻接表的特点如下： (1) 邻邻接接表表表表示示不不唯唯一一。这这是是因因为为在在每每个个顶顶点点对对应应的的单单链链表表中中,各各边边结结点点的的链链接接次次序序可可以以是是任任意意的的,取取决决于于建建立立邻邻接接表表的的算算法以及边的输入次序。法以及边的输入次序。 (2) 对对于于有有n个个顶顶点点和和e条条边边的的无无向向图图,其其邻邻接接表表有有n个个顶顶点点结结点点和和2e个个边边结结点点。显显然然,在在总总的的边边数数小小于于n(n-1)/2的的情情况况下下,邻邻接接表比邻接矩阵要节省空间。表比邻接矩阵要节省空间。 (3) 对对于于

24、无无向向图图,邻邻接接表表的的顶顶点点vi对对应应的的第第i个个链链表表的的边边结结点点数数目正好是顶点目正好是顶点vi的度。的度。 (4) 对对于于有有向向图图,邻邻接接表表的的顶顶点点vi对对应应的的第第i个个链链表表的的边边结结点点数数目目仅仅仅仅是是vi的的出出度度。其其入入度度为为邻邻接接表表中中所所有有adjvex域域值值为为i的的边边结点数目。结点数目。济舵祁践销久官署亮级莎管盈堤嚣乡厕社瓤又猿威劝鄙鳃仁榔挟狄仪笋讹数据结构第三讲数据结构第三讲27真题演练真题演练（1）无向图的邻接矩阵是一个）无向图的邻接矩阵是一个 （ ） A、对称矩阵、对称矩阵 B、零矩阵、零矩阵 C、上三角矩

25、阵、上三角矩阵 D、非对称矩阵、非对称矩阵（2）关于图的存储叙述中，正确的是（关于图的存储叙述中，正确的是（ ）A、用邻接矩阵存储图，占用的存储空间大小只与图中顶点、用邻接矩阵存储图，占用的存储空间大小只与图中顶点数有关，而与边数无关数有关，而与边数无关B、用邻接矩阵存储图，占用的存储空间大小只与图中边数、用邻接矩阵存储图，占用的存储空间大小只与图中边数有关，而与顶点个数无关有关，而与顶点个数无关C、用邻接表存储图，占用的存储空间大小只与图中顶点数、用邻接表存储图，占用的存储空间大小只与图中顶点数有关，而与边数无关有关，而与边数无关D、用邻接表法存储图，占用的占用的存储空间大小只与图、用邻接表

26、法存储图，占用的占用的存储空间大小只与图中边数有关，而与顶点个数无关中边数有关，而与顶点个数无关钝钾主公骆际栏变粹翌搅睫严权峦咬宾旋咽冕涛综撑汪铆弧卓庙贿瓮化数数据结构第三讲数据结构第三讲28三、图的遍历三、图的遍历 图的遍历算法有图的遍历算法有深度优先搜索算法深度优先搜索算法和和广度优先广度优先搜索算法搜索算法。采用的数据结构是。采用的数据结构是(正正)邻接链表邻接链表。 从给定图中任意指定的顶点从给定图中任意指定的顶点(称为初始点称为初始点)出发出发,按照按照某种搜索方法沿着图的边访问图中的所有顶点某种搜索方法沿着图的边访问图中的所有顶点,使每个顶使每个顶点点仅被访问一次仅被访问一次,这个

27、过程称为图的遍历。这个过程称为图的遍历。 如如果果给给定定图图是是连连通通的的无无向向图图或或者者是是强强连连通通的的有有向向图图,则则遍遍历历过过程程一一次次就就能能完完成成,并并可可按按访访问问的的先先后后顺顺序序得得到到由由该图所有顶点组成的一个序列。该图所有顶点组成的一个序列。猿帕梭配焉尹琅钢郎摩沮垦浦尧荒虑奇沥扣虫惺薛赚谤咒慢像探校犀耙撂数据结构第三讲数据结构第三讲29DFS序列：序列：21034部分合法的部分合法的DFSDFS序列：序列：2 3 0 1 42 3 0 1 4；2 1 0 4 32 1 0 4 3；2 4 3 0 12 4 3 0 1不合法的不合法的DFSDFS序列举

28、例：序列举例：2 0 1 3 42 0 1 3 4腋佬坤余副瘩踞剖五抢厄册馈瘫恕空瑶巷椎滤痕享篙仑纯讨凭小蜂城姐壮数据结构第三讲数据结构第三讲30部分合法的部分合法的BFSBFS序列：序列：2 1 3 4 0;2 3 1 4 0;2 4 1 3 02 1 3 4 0;2 3 1 4 0;2 4 1 3 0不合法的不合法的BFSBFS序列举例：序列举例：2 1 0 3 4 2 1 0 3 4 ；2 3 0 4 12 3 0 4 1但但是是，若若对对上上图图采采用用上上面面的的邻邻接接表表存存储储,假假设设初初始始顶顶点点编编号号v=2, 进进行行广广度度优优先先遍遍历历的的话话，序序列列就是唯一

29、的了。此时的遍历序列如下：就是唯一的了。此时的遍历序列如下：BFS序列：序列：21340险澳渝乱含吃掣麻偏猜豁紫冯使郸丛芍边权棠也际构曾壕业绍渣葡藩泊看数据结构第三讲数据结构第三讲31真题演练真题演练 (1)有有N个顶点、个顶点、E条边且用邻接表存储的有向图条边且用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是进行广度优先遍历，其算法时间复杂度是 （ ） A、O（N） B、O（E） C、O（N+E） D、O（N*E） (2)如果从无向图的任一顶点出发进行一次深度优如果从无向图的任一顶点出发进行一次深度优先遍历即可访问所有顶点，则该图一定是（先遍历即可访问所有顶点，则该图一定是（ ） A

30、. 完全图完全图 B. 连通图连通图 C.有回路有回路 D.一棵树一棵树钢同权吭霍膀幸沿之昔曲祝随涤邑泉鳖丫撵柏痊扬鹊增庞馋膜汗卿馏诊蒜数据结构第三讲数据结构第三讲32四、图的应用四、图的应用最小生成树最小生成树拓扑排序拓扑排序最短路径最短路径关键路径关键路径质类毡缝诫忽侠攀坯仓酝摄碑沽邀秃琢秤塘瓣倪升请盼美签麦葡秀呻震置数据结构第三讲数据结构第三讲33最小生成树生成树的概念生成树的概念 一一个个连连通通图图的的生生成成树树是是一一个个极极小小连连通通子子图图,它它含含有有图图中中全全部部顶点顶点,但只有构成一棵树的但只有构成一棵树的(n-1)条边。条边。 命题：如果在一棵生成树上添加一条边命

31、题：如果在一棵生成树上添加一条边,必定构成一个环。必定构成一个环。因因为为这这条条边边使使得得它它依依附附的的那那两两个个顶顶点点之之间间有有了了第第二二条条路路径径。一一棵棵有有n个个顶顶点点的的生生成成树树(连连通通无无回回路路图图)有有且且仅仅有有(n-1)条条边边,如如果果一一个个图图有有n个个顶顶点点和和小小于于(n-1)条条边边,则则是是非非连连通通图图。如如果果它它多多于于(n-1)条边条边,则一定有回路。则一定有回路。 但是但是,有有(n-1)条边的图不一定都是生成树。条边的图不一定都是生成树。 昌匀埂统曰备休锤孺倚寇鞋胸獭痰燕撕折耀刮扰繁丫时扰洞资灼峨绒讳免数据结构第三讲数据

32、结构第三讲34 由由深深度度优优先先遍遍历历得得到到的的生生成成树树称称为为深深度度优优先先生生成成树树；由由广广度度优优先先遍遍历历得得到到的的生生成成树树称称为为广广度度优优先先生生成成树树。这这样样的的生生成成树树是是由由遍遍历历时时访访问问过过的的n个个顶顶点点和和遍遍历历时时经经历历的的n-1条条边组成。边组成。 对于非连通图对于非连通图,每个连通分量中的顶点集和遍历时走过每个连通分量中的顶点集和遍历时走过的边一起构成一棵生成树的边一起构成一棵生成树,各个连通分量的生成树组成非连各个连通分量的生成树组成非连通图的生成森林。通图的生成森林。 耙孕胳段泪锚挠祸义绊扶浴圣超于嫁蝎零厩趟赌喧

33、淀陇讣咐分蔼撒冶蹋褥数据结构第三讲数据结构第三讲35从从1 1号顶点开始的深度优先号顶点开始的深度优先遍历序列：遍历序列：1 0 3 2 41 0 3 2 4从从1 1号顶点开始的深度优先号顶点开始的深度优先遍历序列：遍历序列：1 0 2 3 41 0 2 3 4匡计持铺罢薯贷绎铅载奎露沉呈朴铜牺萍抹辙丸驾猿综保禽储狼咖荤毛晕数据结构第三讲数据结构第三讲36普里姆算法普里姆算法 普里姆普里姆(Prim)算法是一种构造性算法。算法是一种构造性算法。 假假 设设 G=(V,E)是是 一一 个个 具具 有有 n个个 顶顶 点点 的的 带带 权权 连连 通通 无无 向向 图图,T=(U,TE)是是G的

34、的最最小小生生成成树树,其其中中U是是T的的顶顶点点集集,TE是是T的的边边集集,则由则由G构造最小生成树构造最小生成树T的步骤如下：的步骤如下： 醒豹恐枷蹈役暑荐旧酪斋拌前允媳汾杨哑遏和酞捏峨驼闻昆膛柒幕亩黍铁数据结构第三讲数据结构第三讲37 (1) 初始化初始化U=v。v到其他顶点的所有边为候选边；到其他顶点的所有边为候选边； (2) 重复以下步骤重复以下步骤n-1次次,使得其他使得其他n-1个顶点被加入到个顶点被加入到U中：中： 从候选边中挑选权值最小的边输出从候选边中挑选权值最小的边输出,设该边在设该边在V-U中的中的顶点是顶点是k,将将k加入加入U中中,删除和删除和k关联的边；关联的

35、边； 考察当前考察当前V-U中的所有顶点中的所有顶点vi,修改候选边：若修改候选边：若(vk,vi)的权值小于原来和的权值小于原来和vi关联的候选边关联的候选边,则用则用(vk,vi)取代后者作为候取代后者作为候选边。选边。普里姆算法普里姆算法过程过程：vkUVUkiUVUv哺巷昨翁而酗黔入烂伺苇犹涵域兢酗空婿镑起声雨其疵随屑防幅娇岂棒超数据结构第三讲数据结构第三讲3801234651951418271682131270432165148531621 012 34 56closestlowcost1918140000000001648412403337213 025 000U V-U(i, c

36、losesti)iU，closestiVU候选边候选边 ：待陇结舷橡惋公诱庇奋敢圣框漆句宴谚首骇炳挚昧橇朔窿形掏宰角释旦胆数据结构第三讲数据结构第三讲398.4.5 克鲁斯卡尔算法克鲁斯卡尔算法 克克鲁鲁斯斯卡卡尔尔(Kruskal)算算法法是是一一种种按按权权值值的的递递增增次次序序选选择择合合适适的的边边来来构构造造最最小小生生成成树树的的方方法法。假假设设G=(V,E)是是一一个个具具有有n个个顶点的带权连通无向图顶点的带权连通无向图,T=(U,TE)是是G的最小生成树。的最小生成树。 (1) 置置U的初值等于的初值等于V(即包含有即包含有G中的全部顶点中的全部顶点),TE的初的初值为空

37、集值为空集(即图即图T中每一个顶点都构成一个分量中每一个顶点都构成一个分量)。 (2) 将图将图G中的边按权值从小到大的顺序依次选取：若选中的边按权值从小到大的顺序依次选取：若选取的边未使生成树取的边未使生成树T形成回路形成回路,则加入则加入TE；否则舍弃；否则舍弃,直到直到TE中包含中包含(n-1)条边为止。条边为止。剥姿辆见牟属本陇犊好恿材药柜勒因非截镜犀蓑孜息牛折检验愤折嚷菜霹数据结构第三讲数据结构第三讲40035214516354652025314NOViVjW1021235231434254503561257235801692461045660033110000届誊罪塌怒剩坑丘诺噪害

38、鄙高涉巧卜迹服槛宝章恒嘲磺遍叙盆斯虾谰郭惊数据结构第三讲数据结构第三讲411901234655141827168213127呈塘阶袍否氧峡渐糠隧却苏谨袱腻玄装赊蛮菜钩梳噪锰章政涸皿童吧拘此数据结构第三讲数据结构第三讲42真题演练真题演练例：下列关于最小生成树的叙述中，正确的例：下列关于最小生成树的叙述中，正确的是是 （ ）A、最小生成树的代价是唯一的、最小生成树的代价是唯一的B、所有权值最小的边一定会出现在所有的、所有权值最小的边一定会出现在所有的最小生成树中最小生成树中C、使用普里姆算法从不同顶点开始得到的、使用普里姆算法从不同顶点开始得到的最小生成树一定相同最小生成树一定相同D、使用普里姆

39、算法和克鲁斯卡尔算法得到、使用普里姆算法和克鲁斯卡尔算法得到的最小生成树一定相同的最小生成树一定相同乎妖桃嘲挡凰疮牢讯熬陪渠浦完粳砷镰其亏浮瘤卫坞等践变心墩硷拉辖希数据结构第三讲数据结构第三讲43真题演练真题演练已知无向网的邻接矩阵如图所示，要求：已知无向网的邻接矩阵如图所示，要求：（1）画出该图；）画出该图；（2）按照克鲁斯卡尔算法给出该网的最小）按照克鲁斯卡尔算法给出该网的最小生成树的过程。生成树的过程。 4 3 4 5 6 9 3 5 5 6 6 5 7 6 5 4 9 7 3 4 3 6 3 2 5 2 6 6 4 6 瘪在肃仁贩侨泞试羚钞项退绥约哲虫车丧域喂挝孝枝戒奶鬃利实刺赠谓脑数

40、据结构第三讲数据结构第三讲44（1）该无向网如下图所示）该无向网如下图所示0 V11 V22 V33 V44 V55 V66 V77 V8V1V3V8V2V4V5V7V63654623 67953465娥娇举首纂烤板幂莱贤赏浆粕杖诸盟赘椰獭仅锨芍屏改赘闹膜葬牡矽史券数据结构第三讲数据结构第三讲45(2)生成过程如下：生成过程如下：V1V3V8V2V4V5V7V6V1V3V8V2V4V5V7V62V1V3V8V2V4V5V7V623V1V3V8V2V4V5V7V6233V1V3V8V2V4V5V7V62334V1V3V8V2V4V5V7V6233442V1V3V8V2V4V5V7V633445V

41、1V3V8V2V4V5V7V6334455履旁涛啃拿誉萝幌栽谰槽硕恍哩淖隔晕烫维芦稗腾渠钟墨玩急娠丝捍苯镑数据结构第三讲数据结构第三讲46最短路径最短路径 对对于于带带权权的的图图,考考虑虑路路径径上上各各边边上上的的权权值值,则则通通常常把把一一条条路路径径上上所所经经边边的的权权值值之之和和定定义义为为该该路路径的径的路径长度路径长度或称或称带权路径长度带权路径长度。 从从源源点点到到终终点点可可能能不不止止一一条条路路径径,把把带带权权路路径径长长度度最最短短的的那那条条路路径径称称为为最最短短路路径径,其其路路径径长长度度(权值之和权值之和)称为称为最短路径长度最短路径长度或者或者最短

42、距离最短距离。砷捐寒殿桃卡缀替麓复诧眷箭餐屈赖麻答醚愚语猩囤喻驮慕洽诫勒潞侈虹数据结构第三讲数据结构第三讲47从一个顶点到其余各顶点的最短路径从一个顶点到其余各顶点的最短路径 问问题题：给给定定一一个个带带权权有有向向图图G与与源源点点v,求求从从v到到G中中其其他顶点的最短路径他顶点的最短路径,并限定各边上的权值大于或等于并限定各边上的权值大于或等于0。 幢榷夫国颊嫉摈摄抄停卢仁辆柳槽贫铅烬总万颊抓爽蜗早氟远积票向辆俞数据结构第三讲数据结构第三讲48 采用采用狄克斯特拉狄克斯特拉(Dijkstra)算法算法求解求解 基基本本思思想想是是：设设G=(V,E)是是一一个个带带权权有有向向图图,

43、把把图图中中顶顶点点集集合合V分成两组：分成两组： 第第一一组组为为已已求求出出最最短短路路径径的的顶顶点点集集合合(用用S表表示示,初初始始时时S中中只只有有一一个个源源点点,以以后后每每求求得得一一条条最最短短路路径径v,vk,就就将将vk加加入入到到集集合合S中中,直到全部顶点都加入到直到全部顶点都加入到S中中,算法就结束了算法就结束了) 第二组为其余未确定最短路径的顶点集合第二组为其余未确定最短路径的顶点集合(用用U表示表示)。砖甥沁倘矿迢抵途砒熬邻济瘟理因笼式操渺苑辫疲门妖廖较恢耗魏贩刽朴数据结构第三讲数据结构第三讲49 按按最最短短路路径径长长度度的的递递增增次次序序依依次次把把第

44、第二二组组的的顶顶点点加加入入S中中。在在加加入入的的过过程程中中,总总保保持持从从源源点点v到到S中中各各顶顶点点的的最最短短路径长度路径长度不大于不大于从源点从源点v到到U中任何顶点的最短路径长度。中任何顶点的最短路径长度。 此此外外,每每个个顶顶点点对对应应一一个个距距离离,S中中的的顶顶点点的的距距离离就就是是从从v到到此此顶顶点点的的最最短短路路径径长长度度,U中中的的顶顶点点的的距距离离从从v到到此此顶顶点点只包括只包括S中的顶点为中间顶点的当前最短路径长度中的顶点为中间顶点的当前最短路径长度。伶癸沫焰标秽奔遗氖颗砒霜编汛揉爱福氰怠陆韶卵蛔轿理挽陌孜杯巷价德数据结构第三讲数据结构第

45、三讲50 (1) 初初始始时时,S只只包包含含源源点点,即即S=v,v的的距距离离为为0。U包包含含除除v外外的的其其他他顶顶点点,U中中顶顶点点u距距离离为为边边上上的的权权(若若v与与u有有边边)或或(若若u不是不是v的出边邻接点的出边邻接点)。即图的邻接矩阵中即图的邻接矩阵中v所在的行元素值。所在的行元素值。 (2) 从从U中中选选取取一一个个距距离离v最最小小的的顶顶点点k,把把k加加入入S中中(该该选选定定的的距离就是距离就是v到到k的最短路径长度的最短路径长度)。 (3) 以以k为为新新考考虑虑的的中中间间点点,修修改改U中中各各顶顶点点的的距距离离：若若从从源源点点v到到顶顶点点

46、u(uU)的的距距离离(经经过过顶顶点点k)比比原原来来距距离离(不不经经过过顶顶点点k)短短,则则修修改改顶顶点点u的的距距离离值值,修修改改后后的的距距离离值值为为顶顶点点k的的距距离离加加上上边边上的权。上的权。 (4) 重复步骤重复步骤(2)和和(3)直到所有顶点都包含在直到所有顶点都包含在S中。中。狄克斯特拉算法的过程狄克斯特拉算法的过程檄拢酞瓜吱往卤型铰须粘丧抱挞杠祝芦童唇谓嵌焉捆搀伎铭辛雷娜宗康豢数据结构第三讲数据结构第三讲51顶点顶点V到到j的最小距离的最小距离MIN(cvk+wkj,cvj)炽昧吝兢窍搞敬牲帮缩丹斧税赦棘月中姐沏赁炙究点附希稍呐伐媚珊斑烫数据结构第三讲数据结构

47、第三讲52 S U dist 0 1 2 3 4 5 600 1,2,3,4,5,6 0,4,6,6, 1,2,3,4,5,6 0,4,6,6, 0,0,1 1 2,3,4,5,6 0,4, 2,3,4,5,6 0,4,5 5,6,6,1111, , 0,1,0,1,2 2 3,4,5,6 3,4,5,6 0,4,5,6,11, 0,4,5,6,11,9 9,0,1,2,0,1,2,3 3 4,5,6 4,5,6 0,4,5,6,11,9, 0,4,5,6,11,9, 0,1,2,3,0,1,2,3,5 5 4,6 4,6 0,4,5,6, 0,4,5,6,1010,9,9,1717 0,1,

48、2,3,5,0,1,2,3,5,4 4 6 6 0,4,5,6,10,9, 0,4,5,6,10,9,1616 0,1,2,3,5,4,0,1,2,3,5,4,6 6 0,4,5,6,10,9,16 0,4,5,6,10,9,16 path 0 1 2 3 4 5 60,0,0,0,-1,-1,-1 0,0,0,0,-1,-1,-1 0,0,0,0,1 1,0, ,0, 1 1,-1,-1,-1,-10,0,1,0, 1, 0,0,1,0, 1, 2 2,-1,-10,0,1,0, 1, 2,-10,0,1,0, 1, 2,-10,0,1,0, 0,0,1,0, 5 5, 2, , 2, 5

49、5 0,0,1,0, 5, 2, 0,0,1,0, 5, 2, 4 4 0,0,1,0, 5, 2, 40,0,1,0, 5, 2, 4起勿吟谰昆这术铸章约媚阎郊覆舶山亡图帜榴染低挛控肋竭蜕殖安淖痰憾数据结构第三讲数据结构第三讲53438164256147660123456distpath004660000040115 5969101711525101641656201儡骤多敝驭时姑答咱纹腰萍赵魂荫灯馋差内伶设外坞州侧施榴可侧汹扛苔数据结构第三讲数据结构第三讲548.5.3 每对顶点之间的最短路径每对顶点之间的最短路径 问问题题：对对于于一一个个各各边边权权值值均均大大于于零零的的有有向向图图

50、,对对每每一一对对顶顶点点vivj,求出求出vi与与vj之间的最短路径和最短路径长度。之间的最短路径和最短路径长度。 可可以以通通过过以以每每个个顶顶点点作作为为源源点点循循环环求求出出每每对对顶顶点点之之间间的的最最短短路路径径。除除此此之之外外,弗弗洛洛伊伊德德(Floyd)算算法法也也可可用用于于求求两两顶顶点点之间最短路径。之间最短路径。 院淳冀郊叮围跪女栖瘫伐执能物巷脚侧舷诉借侥郧晨复掂辫庞玉荐相畔睦数据结构第三讲数据结构第三讲55 假假设设有有向向图图G=(V,E)采采用用邻邻接接矩矩阵阵cost存存储储,另另外外设设置置一一个个二二维维数数组组A用用于于存存放放当当前前顶顶点点之

51、之间间的的最最短短路路径径长长度度,分分量量Aij表示当前顶点表示当前顶点vi到顶点到顶点vj的最短路径长度。的最短路径长度。 弗弗洛洛伊伊德德算算法法的的基基本本思思想想是是递递推推产产生生一一个个矩矩阵阵序序列列A0,A1,Ak,An,其其中中Akij表表示示从从顶顶点点vi到到顶顶点点vj的的路路径径上所经过的顶点编号不大于上所经过的顶点编号不大于k的最短路径长度。的最短路径长度。四霸长脉机秧翟床涝爽县已续烽疫格易弯嫁氮腑伦苔涕汹埂吓农男童意臂数据结构第三讲数据结构第三讲56 初初始始时时,有有A-1ij=costij。当当求求从从顶顶点点vi到到顶顶点点vj的的路路径径上上所所经经过过

52、的的顶顶点点编编号号不不大大于于k+1的的最最短短路路径径长长度度时时,要要分分两种情况考虑：两种情况考虑： 一一种种情情况况是是该该路路径径不不经经过过顶顶点点编编号号为为k+1的的顶顶点点,此此时时该该路路径径长长度度与与从从顶顶点点vi到到顶顶点点vj的的路路径径上上所所经经过过的的顶顶点点编编号号不不大大于于k的最短路径长度相同；的最短路径长度相同； 另另一一种种情情况况是是从从顶顶点点vi到到顶顶点点vj的的最最短短路路径径上上经经过过编编号号为为k+1的顶点。的顶点。忘照信议镭赃祷戌盖指来参避讽渣寡筹焰窗智臀堑皿指塔账天敢蕴谋乏沂数据结构第三讲数据结构第三讲57Ak+1i,j=MI

53、N(Aki,j,Aki,k+1+Akk+1,j)狡羌璃丧抡涅绅鞍竖傣彪匣山修书灌犬舀贿雄觉庄还鸳铝姆争涝冉虱糊酷数据结构第三讲数据结构第三讲58 那么那么,该路径可分为两段该路径可分为两段: (1) 从顶点从顶点vi到顶点到顶点vk+1的最短路径的最短路径; (2) 从顶点从顶点vk+1到顶点到顶点vj的最短路径。的最短路径。 此此时时最最短短路路径径长长度度等等于于这这两两段段路路径径长长度度之之和和。这这两两种种情情况况中中的的较较小小值值,就就是是所所要要求求的的从从顶顶点点vi到到顶顶点点vj的的路路径径上上所所经经过的顶点编号不大于过的顶点编号不大于k+1的最短路径。的最短路径。筋嘉

54、著印迪女熊琢跨方湖袜涂谬斑灸木淹杖骋滦乘抗望冀托烯懒齿洼留拔数据结构第三讲数据结构第三讲59 弗洛伊德思想可用如下的表达式来描述：弗洛伊德思想可用如下的表达式来描述： A-1ij=costij Ak+1ij=MIN Akij, Akik+1+Akk+1j (0kn-1)窗上醒傈蔬谚院煌茄殊镇乔游拷怂匙觅蕉裙峨予熏恨另竞铲附乒贫强惮淮数据结构第三讲数据结构第三讲60 采用弗洛伊德算法求解过程采用弗洛伊德算法求解过程 012353273124歉航咋铱倔邪巴斗闭涨慨境报势曙淑螺拧慨医犁抢门躬陈蛔肤咽莹候捞室数据结构第三讲数据结构第三讲61 考考虑虑顶顶点点v0,A0ij表表示示由由vi到到vj,经由

55、顶点经由顶点v0的最短路径。的最短路径。v2-v0-v1：不改变。：不改变。v2-v0-v3：不改变。：不改变。012353273124恭膛债姻塑败疲踢言季屁谱些唇印扎肠辞损而媚釉映域矩别德之矛岂闭搬数据结构第三讲数据结构第三讲62 考考虑虑顶顶点点v1,A1ij表表示示由由vi到到vj,经由顶点经由顶点v1的最短路径。的最短路径。v0-v1-v2,路路 径径 长长 度度 为为 9,将将A02改为改为9。path02改为改为1。 012353273124庭判约筑颗斜罚粟父战芝绣雏哉唤曾境酗誓支趣妈烹滞聋赎蠕提鬼砾壳台数据结构第三讲数据结构第三讲63 考考虑虑顶顶点点v2,A2ij表表示示由由v

56、i到到vj,经由顶点经由顶点v2的最短路径。的最短路径。v3-v2-v0,长长度度为为4,将将A30改改为为4；v3-v2-v1,长度为长度为4,将将A31改为改为4。v1-v2-v0,长度为长度为7,将将A10改为改为7。将将path30、path31和和path10均改为均改为2。因此。因此,有：有： 012353273124皿瑶蛤诸或锁钎方笆稻虱架矛秋症舜寄晦蛀赫纂苗标吵全狰浩亮撇末滑液数据结构第三讲数据结构第三讲64 考虑顶点考虑顶点v3,A3ij表示由表示由vi到到vj,经由顶点经由顶点v3的最短路径。的最短路径。 v0-v3-v2：长度为：长度为8,A02改为改为8； v1-v3-

57、v2-v0,长度为长度为6,A10改为改为6； v1-v3-v2,长度为长度为3, A12改为改为3。将将path02、path10后后path12均改为均改为3。 012353273124锻鹊卧饯纷碱芍氢逼葛宠征狰抽掳或状钦扼困硝外弛烃琼搀浴非裴猴抡洽数据结构第三讲数据结构第三讲65从从0到到0路径为：路径为：0,0路径长度为：路径长度为：0从从0到到1路径为：路径为：0,1路径长度为：路径长度为：5从从0到到2路径为：路径为：0,3,2路径长度为：路径长度为：8从从0到到3路径为：路径为：0,3路径长度为：路径长度为：7从从1到到0路径为：路径为：1,3,2,0路径长度为：路径长度为：6从

58、从1到到1路径为：路径为：1,1路径长度为：路径长度为：0从从1到到2路径为：路径为：1,3,2 路径长度为：路径长度为：3从从1到到3路径为：路径为：1,3路径长度为：路径长度为：2A=Path=凰讶驻陌织脖胺牙供奋雌贮鞍拔蓉鹊间寇位霸霍澡闸拷样让窥怎抿李挨颇数据结构第三讲数据结构第三讲66从从2到到0路径为：路径为：2,0路径长度为：路径长度为：3从从2到到1路径为：路径为：2,1路径长度为：路径长度为：3从从2到到2路径为：路径为：2,2路径长度为：路径长度为：0从从2到到3路径为：路径为：2,3路径长度为：路径长度为：2从从3到到0路径为：路径为：3,2,0 路径长度为：路径长度为：4

59、从从3到到1路径为：路径为：3,2,1 路径长度为：路径长度为：4从从3到到2路径为：路径为：3,2路径长度为：路径长度为：1从从3到到3路径为：路径为：3,3路径长度为：路径长度为：0篷壹训弃耻蕉么炳武蛇追衙行钓硬鸥揭辅丢萝哭绘揉阑星布吏亢靶铝厕蝉数据结构第三讲数据结构第三讲67拓朴排序拓朴排序设设G=(V,E)是一个具有是一个具有n个顶点的有向图个顶点的有向图,V中顶点序列中顶点序列v1,v2,vn称为一个称为一个拓扑序列拓扑序列,当且仅当该顶点序列满当且仅当该顶点序列满足下列条件：足下列条件： 若若是是图图中中的的边边(即即从从顶顶点点vi到到vj有有一一条条路路径径),则在序列中顶点则

60、在序列中顶点vi必须排在顶点必须排在顶点vj之前。之前。 在在一一个个有有向向图图中中找找一一个个拓拓扑扑序序列列的的过过程程称称为为拓拓扑扑排序。排序。 丁滁灶完郴慌鸳驶坯婆烟其阳问腋充申林札揉葵胜痈咱庶尸哇炽撩担布燥数据结构第三讲数据结构第三讲68 (1) 从从有有向向图图中中选选择择一一个个没没有有前前驱驱(即即入入度度为为0)的的顶顶点点并且输出它。并且输出它。 (2) 从从网网中中删删去去该该顶顶点点,并并且且删删去去从从该该顶顶点点发发出出的的全全部部有向边。有向边。 (3) 重重复复上上述述两两步步,直直到到剩剩余余的的网网中中不不再再存存在在没没有有前前驱驱的顶点为止。的顶点为

61、止。拓扑排序步骤拓扑排序步骤涩撩坯哥诧蕉附氢津厌睡悟身溶稠银怨锥雇哥近丙芹枫厢爵切瓮局弯贾筛数据结构第三讲数据结构第三讲690 0 12 4 5 3 0 12 4 5 3 41253全部可能的拓扑排序序列：041253 041523 045123450123 401253 405123 401523灼贱剂埋狮姐挫弧肾讶曼狡醚愚臀玛诫庄挤浪感感鼎菊绘撑投稀谗玛蚂挡数据结构第三讲数据结构第三讲70关键路径关键路径 若用带权有向图若用带权有向图(DAG)描述工程的预计进度描述工程的预计进度,以顶点以顶点表示事件表示事件,有向边表示活动有向边表示活动,边边e的权的权c(e)表示完成活动表示完成活动e所

62、需的时间所需的时间(比如天数比如天数),或者说活动或者说活动e持续时间。持续时间。 图中入度为图中入度为0的顶点（的顶点（源点源点）的）的开始事件开始事件(如开工仪如开工仪式式),出度为出度为0的顶点（的顶点（汇点汇点）表示工程）表示工程结束事件结束事件。则称。则称这样的有向图为这样的有向图为AOE网网(Activity On Edge)。 烧坷蝎唐哪跟惋股犊峻喀豹作撑馅着兢亿刷捅扁勇别憾刷拳廉现幕金翱若数据结构第三讲数据结构第三讲71v0v6v5v4v3v2v1v7v8a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=6a10=11a12=5a8=4a11=2 一个一个AO

63、E网网源点源点汇点汇点侩倾舟萎遣肘夺帛恬惕嘴侄杭城唆躲场址涸害和鸥珐李覆蛋锐佑新锣帕裸数据结构第三讲数据结构第三讲72 几个定义：几个定义： (1) 事件事件v的最早可发生时间：假设事件的最早可发生时间：假设事件x是源点是源点,事件事件y为汇点为汇点,并规定事件并规定事件x的发生时间为的发生时间为0。定义图中任一事件。定义图中任一事件v的最的最早早(event early)可发生时间可发生时间ve(v)等于等于x到到v所有路径长度的最大所有路径长度的最大值值,即：即： ve(v)= 上式中的上式中的MAX是对是对x到到v的所有路径的所有路径p取最大值取最大值,c(p)表示路表示路径径p的长度的

64、长度(路径上边长之和路径上边长之和) ,即：即：c(p)= 完成整个工程所需的最少时间完成整个工程所需的最少时间,等于事件等于事件y的最早可发生时的最早可发生时间间ve(y)。 惫劝田影禽醚间帛雍废锡车慈丽池坯梆个梅茨见讫灸躬冀瞎迭榨菲步例病数据结构第三讲数据结构第三讲73v0v6v5v4v3v2v1v7v8a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=6a10=11a12=5a8=4a11=2 源点源点汇点汇点粗耐沫宿俄冯廓益肪入泻悉盈通缝挚哉异诣前拳忱席扫趴椽亢佛贤屏蕾侣数据结构第三讲数据结构第三讲74 整个工程完成的最短时间指的是整个工程完成的最短时间指的是：从有向

65、图的源点到汇点的：从有向图的源点到汇点的最长路径的长度最长路径的长度，具有最大长度的路径叫关键路径。，具有最大长度的路径叫关键路径。 “关键活动关键活动”指的是：该弧上的权值增加将使有向图上的指的是：该弧上的权值增加将使有向图上的最长路径的长度增加。最长路径的长度增加。 注意：在一个注意：在一个AOE网中，可以有不止一条的关键路径。网中，可以有不止一条的关键路径。 v0v6v5v4v3v2v1v7v8a1=3a2=10a3=9a4=13a5=12a6=7a7=8a9=6a10=11a12=5a8=4a11=2 源点源点汇点汇点因玉攻疑躺粪妒规泡膨蓑哲劲捌犯微舒螟洪蚁锣岿逞肆割需操数怨么碧固数据

66、结构第三讲数据结构第三讲75 (2) 事事件件v的的最最迟迟可可发发生生时时间间：定定义义在在不不影影响响整整个个工工程程进进度度的的前前提提下下,事事件件v必必须须发发生生的的时时间间称称为为v的的最最迟迟(event late)可可发发生生时时间间,记记作作vl(v)。vl(v)应应等等于于ve(y)与与v到到y的的最最长长路路径径长长度度之之差差(y是汇点是汇点),即：即： vl(v)=ve(y) - (3) 关关键键活活动动:若若活活动动v满满足足ve(v)+c(ai)=vl(w),则则称称活活动动ai为为关键活动，关键活动，ai=。 对对关关键键活活动动来来说说, ,不不存存在在富富

67、余余时时间间。显显然然, ,关关键键路路径径上上的的活活动动都都是是关关键键活活动动。找找出出关关键键活活动动的的意意义义在在于于, ,可可以以适适当当地地增增加加对对关关键键活活动动的的投投资资( (人人力力、物物力力等等),),相相应应地地减减少少对对非非关关键键活活动动的投资的投资, ,从而减少关键活动的持续时间从而减少关键活动的持续时间, ,缩短整个工程的工期。缩短整个工程的工期。 石吧挚描悉溃谩篷竭仿痢枝诚啊惠漫流葫酶旷涧郑奋啮梯衣霍边符酵纪卯数据结构第三讲数据结构第三讲76ve(v)最早开始时间ve(v)最迟开始时间v000v139v21010v31223v42222v51717v

68、62031v72828v83333迫日唾鲸换懊兵宜砖卉溪逃于陀增球穷玛柄番魂场亦群臭么佛咎苔爽翼赌数据结构第三讲数据结构第三讲77 只要计算出各项点的只要计算出各项点的ve(v)和和vl(v)的值的值,就能找出所有的关就能找出所有的关键活动。为了便于计算键活动。为了便于计算,引入下面两个递推式引入下面两个递推式,其中其中,x和和y分分别是源点和汇点。别是源点和汇点。 ve(x)=0 ve(w)= wx上式中的上式中的MAX对所有射入对所有射入w的边的边取最大值。取最大值。 vl(y)=0 vl(v)= vy水隙篓沥园峻便蚀资立僚随漫阐骇禾茹煎优孝率唬妹痢刻雌警占陇瓮疤务数据结构第三讲数据结构第

69、三讲78 (1) 对于源点对于源点x,置置ve(x)=0； (2) 对对AOE网网进进行行拓拓扑扑排排序序。如如发发现现回回路路,工工程程无无法法进进行行,则则退退出；否则继续下一步。出；否则继续下一步。 (3) 按按顶顶点点的的拓拓扑扑次次序序,反反复复用用式式8.4,依依次次求求其其余余各各项项点点v的的ve(v)值值。(实实际际上上,步步骤骤(2)和和步步骤骤(3)可可以以合合在在一一起起完完成成,即即一一边边对顶点进行拓扑排序对顶点进行拓扑排序,一边求出各点的一边求出各点的ve(v)之值。之值。) (4) 对于汇点对于汇点y,置置vl(y)=ve(y)； 求求AOE网的关键活动的过程网

70、的关键活动的过程贼靠岿假嗜讫侈憨僻旗镇乘危厚壤剥耸促转人笛旺曲缝相赠欲豫哮坡侍拙数据结构第三讲数据结构第三讲79 (5) 按按顶顶点点拓拓扑扑次次序序之之逆逆序序,反反复复用用式式8.5,依依次次求求其其余余各各项项点点v的的vl(v)的的值值。即即对对v射射出出的的所所有有边边,检检查查是是否否满满足足式式8.3,若若是是,则则输出该边的有关信息输出该边的有关信息,指明该边所对应的活动是关键活动。指明该边所对应的活动是关键活动。 (6) 活活动动ai的的最最早早开开始始时时间间e(i)是是该该活活动动的的起起点点所所表表示示的的事事件件最最早发生时间。如果由边早发生时间。如果由边表示活动表示

71、活动ai,则有则有e(i)=ve(j)。 (7) 活活动动ai的的最最迟迟开开始始时时间间l(i)是是该该活活动动的的终终点点所所表表示示事事件件的的最最迟迟发发生生时时间间与与该该活活动动的的所所需需时时间间之之差差。如如果果用用边边表表示示活活动动ai,则有则有l(i)=vl(k)-ai所需时间。所需时间。勒歼呸此莲嗜诞异淹躇括翠脓肖殴厢徘钮视含铺秒晃赞宠懦郡岳伦低穴圆数据结构第三讲数据结构第三讲80 (8) 一一个个活活动动ai的的最最迟迟开开始始时时间间l(i)和和其其最最早早开开始始时时间间e(i)的的差差额额d(i)=l(i)-e(i)是是该该活活动动完完成成的的时时间间余余量量(

72、富富余余时时间间)。它它是是在在不不增增加加完完成成整整个个工工程程所所需需的的总总时时间间的的情情况况下下,活活动动ai可以拖延的时间。可以拖延的时间。 (9) 当一活动的时间余量为零时当一活动的时间余量为零时,说明该活动必须如期完说明该活动必须如期完成成,否则就会拖延完成整个工程的进度。所以我们称否则就会拖延完成整个工程的进度。所以我们称l(i)-e(i)=0,即即l(i)=e(i)的活动的活动ai是关键活动。是关键活动。 键愉软都跟葵蔷昆弹株藤枷某千狸晃沤驴浅焙雀浊戍萎订坚喘落逝钙俯尤数据结构第三讲数据结构第三讲81计算各事件的计算各事件的ve(v)如下：如下：ve(A)=0,ve(B)

73、=ve(A)+c(a1)=6ve(C)=ve(A)+c(a2)=4ve(D)=ve(A)+c(a3)=5ve(E)=max(ve(B)+c(a4),ve(C)+c(a5)=max7,5=7属阑血龙瘁段润颜滤跃沦厩宴蚀宗币菊伍盘户擅粕铸搓胚珠纷支摹俩练滞数据结构第三讲数据结构第三讲82ve(F)=ve(E)+c(a7)=16ve(G)=ve(E)+c(a8)=14ve(H)=ve(D)+c(a6)=7ve(I)=maxve(F)+c(a10),ve(G)+c(a11),ve(H)+c(a9) =max(18,18,11=18奢处揣饼叼施冰琉婶示撕疥轻挂按汕廓峡谣释甥衫则弊瀑猎妻厦涣率行柱数据结构

74、第三讲数据结构第三讲83计算各事件的计算各事件的vl(v)如下：如下： vl(I)=ve(I)=18 vl(F)=vl(I)-c(a10)=16 vl(G)=vl(I)-c(a11)=14 vl(H)=vl(I)-c(a9)=14父索东字钩隋伞义舌秩唯宴既毖堑森邹颠番浪瑞寄抓碳缅席旁冬砾擎惩啊数据结构第三讲数据结构第三讲84 vl(E)=min(vl(F)-c(a7),vl(G)-c(a8)=7,7=7 vl(D)=vl(H)-c(a6)=12 vl(C)=vl(E)-c(a5)=6 vl(B)=vl(E)-c(a4)=6 vl(A)=min(vl(B)-c(a1),vl(C)-c(a2),v

75、l(D)-c(a3)=0,2,7=0旁望哟蒲盒绪翁魏替彬老鞘摹苟裴井芽焉借篮痘婴透均房崩廉钎只馏挚自数据结构第三讲数据结构第三讲85 计算各活动的计算各活动的e(a)、l(a)和和d(a)如下：如下： 活动活动a1：e(1)=ve(A)=0,l(1)=vl(B)-6=0,d(1)=0 活动活动a2：e(2)=ve(A)=0,l(2)=vl(C)-4=2,d(2)=2 活动活动a3：e(3)=ve(A)=0,l(3)=vl(D)-5=7,d(3)=7 活动活动a4：e(4)=ve(B)=6,l(4)=vl(E)-1=6,d(4)=0 活动活动a5：e(5)=ve(C)=4,l(5)=vl(E)-

76、1=6,d(5)=2颠呈衫怔借谁日坦山渤胜提碗氓加捡痪渊恩硷卡斑率疗遣罐弘元制甜阴呻数据结构第三讲数据结构第三讲86活动活动a6：e(6)=ve(D)=5,l(6)=vl(H)-2=12,d(6)=7活动活动a7：e(7)=ve(E)=7,l(7)=vl(F)-9=7,d(7)=0活动活动a8：e(8)=ve(E)=7,l(8)=vl(G)-7=7,d(8)=0活动活动a9：e(9)=ve(H)=7,l(9)=vl(G)-4=10,d(9)=3活动活动a10：e(10)=ve(F)=16,l(10)=vl(I)-2=16,d(10)=0活动活动a11：e(11)=ve(G)=14,l(11)=

77、vl(I)-4=14,d(11)=0 溜鸭售充状兄哎讣鲸芦监切快磋竿滋恋港犬旺逞圣桌出非藐烈瞄估玉目靡数据结构第三讲数据结构第三讲87 由此可知由此可知,关键活动有关键活动有a11、a10、a8、a7、a4、a1,因因此关键路径有两条：此关键路径有两条：A-B-E-F-I和和A-B-E-G-I。 估奠匈舜叫半霸钮檀庆撞摈退亢呼麻碍休富匙突流尼吴叙导外钮淮裁溉帐数据结构第三讲数据结构第三讲88v0v5v4v7v3v2v1v6v8a1=5a2=6a3=3a8=5a4=12a5=3a10=4a9=1a12=5a11=4a6=3a7=3a13=2v9a14=2假设一个工程的进度计划用假设一个工程的进度计划用AOE网表示，如图所示。网表示，如图所示。 求出每个事件的最早发生时间和最晚发生时间。求出每个事件的最早发生时间和最晚发生时间。 该工程完工至少需要多少时间该工程完工至少需要多少时间? 求出所有关键路径和关键活动。求出所有关键路径和关键活动。卜误腕惺础斥维昆提虑伟笨氰劲稿揪浸夜则著搬舵瑞化孝视钟唆甘积捻蛊数据结构第三讲数据结构第三讲89