[教学]数据结构与算法基础(第三版)第四章图.ppt

《[教学]数据结构与算法基础(第三版)第四章图.ppt》由会员分享，可在线阅读，更多相关《[教学]数据结构与算法基础(第三版)第四章图.ppt（61页珍藏版）》请在三一办公上搜索。

1、4.1 基本术语 4.2 图的表示4.3 图的搜索算法 4.4 图与树的联系4.5 无向图的双连通性*4.6 有向图的搜索4.7 强连通图4.8 拓扑分类*4.9 关键路径4.10 单源最短路径*4.11 每一对顶点间的最短路径,第四章 图以及与图有关的算法,文虹茶蕉倚臻儒放循壶激海椰玩念亢居剑汗货蛾乔汤鱼晦李甚捂捶御必胎数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,4.1 基本定义/术语,定义：一个图G=（V，E）是一个由非空的有限集 V和一个边集E 所组成的。若E中的每条边都是结点的有序对（v,w），就说该图是有向图（directed grph，digrph）。

2、若E中的每条边是两个不同结点有序对，就说该图是无向图，其边仍表示成（v,w）。,DT.Grph G=(V,R)数据对象v：v是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=VR VR=|v,w V,且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧 的意义或信息,委倒脸扛完钳邦挽易哑吃葛瞥宅怯冕用赡赘佣勿糕瀑吨终壕械即纸朔汉什数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,操作：,Node NEWNODE(G)Void DELNODE(G,v)Void SETSUCC(G,v1,v2)Void DELSUCC(G,v1,v2)Listonode S

3、UCC(G,v1,v2)Lisyonode PRED(G,v)Int ISEDGE(G,v1,v2)Node irstdjVex(G,v)Node NextdjVex(G,v,w),术语：顶点 弧 边 邻接 相邻 依附 路径（路）简单路径 环路 带标号的图（网）连通 连通图 强连通图 连通分量 完全图 完全图 稀疏图 稠密图 子图 度 入度 出度 生成树,润缄萍汞篇彬晓滑泊组参珠茶洛冕肚铲漂富癸告舜镐轰诧缓喉卢杂屉幸鼠数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,4.2 图的表示,1、图的顺序存储邻接矩阵,设图G=(V,E)，V=0，1，n-1 则表示G的邻接矩阵

4、是其元素按下式定义的nxn矩阵:,网的邻接矩阵可定义为：,TD(v i)=ij=ji(n 顶点个数）,j=0,n-1,j=0,n-1,荐很仿胸粟筛叫稽蹦丹话裔鄙泪戚滋罚枯接扣瓦沙僻宜颁隔窜援敝晴宅挨数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,#deine ININITY INT_MX#deine MX_VERTEX_NUM 20Typede enum DG,DN,G,N GrphKind;Typede struct rcCell VRType dj;InoType*ino;rcCell,djMtrix MX_VERTEX_NUMMX_VERTEX_NUM;Type

5、de struct VertexType vexMX_VERTEX_NUM;djMtrix rcs;int vexnum,rcnum;GrphKind kind;Mgrph;,苔褥扁凌垮荐绘戌限玄链导篱诲趟稠肺莱州鲤全领颂约觉炼互滔跃抗冷缠数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,有向图G1,无向图G2,有向网,3,折旭连噪之强乡坡面兽旷捣檬灌鞘扳稠鹤郧圾孕棘府桨致绩摇盲弥魁臃秆数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,2、图的链式存储邻接表（djcency List）,#deine MX_VERTEX_NUM 20Typede

6、struct rcNode int djvex;struct rcNode*nextrc;InoType*ino;rcNode;Typede struct Vnode VertexType dt;rcNode*irstrc;Vnode,djListMX_VERTEX_NUM;Typede struct djList vertices;Int vexnum;Int kind;LGrph;,蛙店盯遮和篇当桑尊蕴欢糜总扼谁多卵石帅磷靳汐测舱逮趋陌已敦衔姚窄数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,无向图G2邻接表,掉过摸哩骆王牵崩揣痰调舀椒戳苯编浑拙恿它远色鹤了钮翌毗

7、看北煞营碑数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,4.3 图的搜索算法,确定遍历起点为保证非连通图的每一顶点都能被访问到，应轮换起点为避免顶点的重复访问，做访问标记,遍历图注意问题：,僧步摧认紫慧培袋泣蜀俩菊蹈乳哲僳韶粕爸侥充淤交嚷论符掳仍涎恶瘪坡数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,1、深度优先搜索DS(Depth-irst serch),首先访问起点，然后依次访问与该起点相关联的每一个顶点，并以该关联顶点为新的起点，继续深度优先遍历。若图中还有未被访问的顶点，则换一个起点，继续深度优先遍历；直到所有的顶点都被访问。,V1

8、,V3,V6,V7,V2,V4,V8,V5,V1,V2,V4,V8,V5,V3,V6,V7,晌挽桔席果靠瘟蛆隐眷膀怒析晦汞留币兜瞳宙醇拙势椭烫狼焦蚤仲比浆冤数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,深度优先遍历：Void DSTrvers(GRPH G,v)or(v=0;v G.vexnum;+v)visited v=LSE;or(v=0;v G.vexnum;+v)i(!visited v)DS(G,v);Void DS(GRPH G,int v)visited v=TRUE;visitunc(v);or(w=irstdjVex(G,v);w;w=Nextdj

9、Vex(G,v,w);i(!visited w)DS(G,w);,图G2的深度优先遍历结果：V1,V4,V3,V5,V2,董辞调泅父宜桅啥榜噎瘟汁漳匡窟匈制绘烩翠莎嚣兼缓头老绿款俘描喷挠数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,T=;/*树边集开始为空*/count=1;/*先深编号计数器*/or(ll v V)while(there exists vertex v V mrked“new”)serch(v)void serch(v)dn v=count;/*对v编号*/count=count+1;mrk v“old”/*访问结点v*/or(ech vertex

10、 wL v)i(w is mrked“new”dd(v,w)to T;/*(v,w)是树边*/serch(w);/*递归搜索*/,输入：L v 表示无向图G的关于v的邻接表输出：每个结点有先深编号的无向图和树边集 T,玫脉苹人探荚锹街监矗署莱渝住男蕴饰硝蚊售头硷譬轴清弥织演泻帮毁粘数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,2、广度优先搜索BS(Bredth-irst serch),V1,V2,V3,V4,V5,V6,V7,V8,V1,V2,V3,V4,V5,V6,V7,V8,首先访问起点，依次访问与该起点相关联的每一个邻接点，然后分别从这些邻接点出发访问它们的邻

11、接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，若图中还有未被访问的顶点，则换一个起点，继续广度优先遍历；直到所有的顶点都被访问。,剪哨耐仅吕道撩陆融吾鸥督十砖基凸稗胁菜鞭枢卤币搽赐痈挤铅汤置梅裳数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,Void BSTrvers(GRPH G,v)or(v=0;v G.vexnum;+v)visited v=LSE;InitQueue(Q);or(v=0;v G.vexnum;+v)i(!visited v)EnQueue(Q,v);while(!QueueEmpty(Q)DeQueue(Q,u);v

12、isited u=TRUE;visit(u);or(w=irstdjVex(G,u);w;w=NextdjVex(G,u,w);i(!visited w)EnQueue(Q,w);,图G2的广度优先遍历结果：V1,V4,V2,V3,V5,凉妹熙湛萎觅脾殉超钞箍敌疤平咐敷筛膜瑚酿吉涂蛛喊痘似誓猾迭窘桔城数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,Void bserch(v)MKENULL(Q);bn v=count;/*先广编号*/count=count+1;mrk v“old”ENQUEUE(v,Q);/*v入队*/while(!EMPTY(Q)v=RONT(Q)

13、;DEQUEUE(Q);or(ech wL v)bn w=count;/*先广编号*/count=count+1;mrk w“old”;ENQUEUE(w,Q);INSERT(v,w),T);/*树边入队*/,输入：L v 表示无向图G的关于v的邻接表输出：每个结点有先广编号的无向图和树边集 T,鲤荧鞘轩淄蝗胖伸谓狸袄男森澄斤疆滑龄格疮哉扑胰捶傻昌钒乏侥率娇前数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,4.4 图与树的联系,4.4.1 先深生成森林和先广生成森林,树边 与 非树边,连通图 一个生成树,非连通图 多个生成树 连通子图（连通分量）,舟志碾瞻裙旬庆诺概爹

14、赎腹峙曰瞥尼捉玖喧拭叫掀女趴怜锄茂伪裤粳愚热数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,4.4.3 最小生成树,4.4.2 无向图与开放树,定义：连通而无环路的无向图称作开放树（ree Tree）,开放树的性质：（1）具有n1个顶点的开放树包含n-1条边（2）如果在开放树中任意加上一条边，便得到一条回路,(证明见教材P154155),设G=(V,E)是一个连通图，E中每一条边(u,v)的权为C(u,v)，也叫做边长。图G的一株生成树(spnning tree)是连接V中所有结点的一株开放树。将生成树中所有边长之总和称为生成树的价(cost)。使这个价最小的生成树称

15、为图G的最小生成树(minimum-cost spnning tree)。,判悍杜告避虽页履枫针停烹绕涵灿例况携次览哼夸拼澡缔观番叫治申掸氏数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,MST性质,设G=(V,E)是一个连通图，在E上定义一个权函数，且(V1,T1),(V2,T2),(Vk,Tk)是 G的任意生成森林。令,又设e=(v,w)是E-T中这样一条边，其权Cv,w最小，而且vV1和wV1。则图G有一棵包含 T e 的生成树，其价不大于包含T的任何生成树的价。,假设N=(V,E)是一个连通网，U是顶点V的一个非空子集。若(u,v)是一条具有最小权值（代价）的

16、边，其中u U,v V-U,则必存在一棵包含边(u,v)的最小生成树。,描述1：,描述2：,广禁烤衡稼脓深古眯扒缄泄平奋眼覆尊民御卷烙贾呛噎焊慧补匪缨扩篡厌数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,MST性质证明,假设网N的任何一棵最小生成树都不包含（u,v），设 T 是连通网上的一棵最小生成树，当将边（u,v）加入到 T中时，由生成树的定义，T 中必包含一条（u,v）的回路。另一方面，由于 T是生成树，则在T上必存在另一条边（u,v），且u和u、v和v之间均有路径相同。删去边(u,v)便可消去上述回路，同时得到另一棵最小生成树T。但因为(u,v)的代价不高于(

17、u,v)，则T的代价亦不高于T，T是包含（u，v）的一棵最小生成树。,幂幽唇沤潞辅榨汽瓶酒逝铱仟申莹音秒缠朔滋篙架镍轩每魂达歇显息疏琅数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,（）,求最小生成树,U,V-U,懒崇矫脑党拌露嘶力抠阶垫摔猪藕岁塑斗帆硝玩民股总楷圣狗筋咐奔棱膀数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,、求最小生成树 Prim 算法,输入：加权无向图（无向网）G=(V,E)，其中v=(1,2,n).输出：G的最小生成树,要点：引入集合U和T。U准备结点集，T为树边集。初值U=1，T=。选择有最小权的边(u,v)，使uU,

18、v(V-U),将v加入 U,（u,v）加入T。重复这一过程，直到U=V.void prim(G,T)T=;U=1;while(U V)!=)设(u,v)是使uU与v(V-U)且权最小的边；T=T(u,v);U=U v;,亩诧彩尘何屹澈霉步寥容潘涣榜残茫哇尽警鳃绷翔剧往殃躬贺厚粟其蓝硅数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,Void Prim(C)Costtype Cn+1n+1;costtype LOWCOSTn+1;int CLOSESTn+1;int i,j,k;costtype min;or(i=2;i=n;i+)LOWCOSTi=C1i;CLOSEST

19、i=1;or(i=2;i=n;i+)min=LOWCOSTi;k=i;or(j=2;j=n;j+)i(LOWCOSTj min)min=LOWCOSTj;k=j;Cout“(”k“,”CLOSESTk“)”end1;LOWCOSTk=ininity;or(j=2;j=n;j+)i(Ckj LOWCOSTj,CLOSESTi为U中的一个顶点边(i,CLOSESTi)具有最小的权LOWCOSTi,纂彝晕吁宋抗议骋权盎号萎鞠艰若澎常我痈奥永离羹镑泞晨耕觅冲瓷翻混数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,、求最小生成树 Kruskl 算法,输入：连通图G=(V,E)，其

20、中v=(1,2,n)，C是关于E中的每条 的权。输出：G的最小生成树,Void Kruskl(V,T)T=V;ncomp=n;while(ncomp 1)从E中取出删除权最小的边（v,u）;i(v 和 u 属于T中不同的连通分量）T=T(v,u)ncomp-;,兆额罢擅策亏做彰门棺洗黔疟怜地风辟衍巡渣句涸浦痊湘贞愉版驻伙次雇数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,籽浆骏灾烛瓮拿洱渊点呆审揭色圆拔垫全铬诅哮较皑酶酝逐池椽蕴像侩书数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,揽钱棕壕津发扯羞笺贾效无做诞笼咽棍覆竭振阐赂伸罢同铁嘛橇迄叮铆

21、伊数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,4.5 无向图的双连通性,先深搜索和先深编号的作用。通过是否遇到回退边，即可确定是否有环路。,液介韦巍蠢圆女痈逼甘赴坑裳哥船俊褐慑弯尿帖丸索畦窃选堑赔屿捣癣渣数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,双连通的无向图是连通的，但连通的无向图未必双连通。一个连通的无向图是双连通的，当且仅当它没有关节点。,定义：若 e1=e2 或者有一条环路包含 e1又包含 e2，则称边e1 和 e2 是等价的。,定义：设 Vi 是 Ei 中各边所连接的点集（1ik）,每个图 Gi=(Vi,E i)叫做 G

22、的一个双连通分量。,双连通分量的性质：性质1：G i 是双连通的（1ik）性质2：对所有的 ij,ViVj 最多包含一个点 性质3：v 是 G 的关节点，当且仅当 vViVj(i j),双连通图的研究意义，如通讯网络。,上述等价关系将E分成等价类E1,E2,Ek,两条不同的边属于同一个类的充要条件是它们在同一个环路上。,挣渣寞木永凸累忆质墩慌昆冰样枪贬查嘘柏荷毖锤没还杖黄伊嗽抿罩颊哇数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,无向图和它的双连通分量,图G,图G的双连通分量,（1）,（2）,（3）,（4）,讥篙效堂峰抨函晴首隘宗唁澈划舍次衔秩曹麦眺脯絮豪怀枣浦蛇赶埔

23、现滔数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,4.5.2 求关节点对图进行一次先深搜索便可求出所有的关节点,若生成树的根有两株或两株以上子树，则此根结点必为关节点（第一类关节点）。因为图中不存在连接不同子树中顶点的边，因此，若删去根顶点，生成树变成生成森林。若生成树中非叶顶点v，其某株子树的根和子树中的其它结点均没有指向v 的祖先的回退边，则v 是关节点（第二类关节点）。因为删去v，则其子树和图的其它部分被分割开来,由先深生成树可得出两类关节点的特性：,去诅腐刷船璃龄映做宜文远鸭钢厨抄蜂拈晕喘孽壬醋瓜敲彭毯潭佃征摘詹数据结构与算法基础(第三版)第四章图数据结构与

24、算法基础(第三版)第四章图,定义 lowv：设对连通图G（V,E）进行先深搜索的先深编号 为dnv，产生的先深生成树为S（V,T），B是 回退边之集。对每个顶点v，lowv定义如下：,dn low,本毅腑谎唁阵蜗垂蹭咒阑厉坠莎糯非稚理萄煌尝帧金萝梳叶刀乡愈跳矛周数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,算法4.5 求无向图的双连通分量,输入：连通的无向图G=(V,E)。Lv表示关于v的邻接表。输出：G的所有双连通分量，每个连通分量由一序列的边组成。算法要点：1.计算先深编号：对图进行先深搜索，计算每个结点v的先深编号 dnv，形成先深生成树S（V,T）。2.计算

25、lowv：在先深生成树上按后根顺序进行计算每个顶点v的 lowv，lowv取下述三个结点中的最小者：(1)dnv；(2)dnw，凡是有回退边（v,w）的任何结点w；(3)lowy，对v的任何儿子y。3.求关节点：(1)树根是关节点，当且仅当它有两个或两个以上的儿子（第一类关节点）；(2)非树根结点v是关节点当且仅当v有某个儿子y，使 lowydnv（第二类关节点）。,难湛臣朴佬膳记钳小民军讳赊澡忻做绷妙援琶稻雄瞧料局次色挥勾耸快挺数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,*4.6 有向图的搜索,DS 和 BS 搜索在有向图和无向图中的区别？,有向图搜索：树边、向

26、前边、回退边、和横边,1、若dnvdnw，则(v,w)是回退边或横边；当产生树边(i,j)时，同时记下j的父亲：therj=i,于是对图中任一条 边(v,w)，当visitedv=“old”,visitedw=“old”且dnvdnw时，由结 点v沿着树边向上(ther中)查找w（可能直到根）；若找到w,则(v,w)是回退边，否则是横边,堰柞瘁铸然武烽葛筛季龄锻注上牢靖对吾晦龟食桨吏舰豢戈欧垣眯蜘蓖黔数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,擒预涛皱新之宠篮距钱诗捷釉貉统柞套徘眉罢咨腑苦顾邱镐愉挝还侗干棕数据结构与算法基础(第三版)第四章图数据结构与算法基础(第

27、三版)第四章图,4.7 强连通性,有向图的强连通分量是满足下列要求的最大子集：对任意两个顶点 x 和 y，都存在一条有向路从 x 到 y，也 存在一条有向路从 y 到 x。,设G=（V,E）是一个有向图，称顶点v,wV是等价的，要么v=w；要么从顶点 v 到 w 有一条有向路，并且从顶点 w 到 v 也有一条有向路。,定义:,设 Ei（1ir）是头、尾均在Vi 中的边集,则Gi=(Vi,E i)称为 G 的一个强连通分量，简称强分量。,定义：,上述等价关系将V分成若干个等价类V1，V2,Vr,强连通图：只有一个强分量的有向图称为强连通图。,培禁澡惯颅亭哆锤溉糠瓜进产卿陋捉晴厨餐琴剿靶糠恐橙跟佬

28、校饺扎费仿数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,分支横边：不在任何强连通分支（量）中的边，如：d,cd注：每个结点都是在某个强连通分支中出现，但某些边的能不 在任何强分支中。归约图：用强分量代表顶点，用分支横边代表有向边的图称为 原图的归约图。显然，归约图是一个不存在环路的有向图，它表示了强分量之间的连通性。,登氯瞥哥殃与妙蓬洽丧樱鸳乍擒欺另恨军消棒竿篡龋叛舀堪盈矛门孪戎返数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,算法:P164,求强连通图的实例,鲸棚轮壁扮亚曰瞒摩蜗构斋贩闷眯狠货阂娩苯辫董溅复哉终嗅蜘等史齿敌数据结构与算法基

29、础(第三版)第四章图数据结构与算法基础(第三版)第四章图,4.8 拓扑分类,给定一个无环路有向图G=(V,E),各结点的编号为V=(1,2,n。要求对每一个结点 i 重新进行编号，使得若 i 是 j 的前导，则有Lbelilbelj。即拓扑分类是将无环路有向图排成一个线性序列，使当从结点 i 到结点j存在一条边，则在线性序列中，将 i 排在 j 的前面。,(+b)*(b*(c+d)+(c+d)*e)*(c+d)*e),有向无环图及其应用,招妻耙掐紫史俊勃受法蛔跳奢冯睡捅却滚解伴蔚希七臀买榔恍衣雄懊借拣数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,例：,可输出结点的入

30、度为零，删去该结点，并将于该顶点相邻的顶点的入度减1,V6,V1,V4,V3,V2,V5,辩习拜杰嗡酿妊氨肇揽呼着襟膳镊亏倡隔瘪譬熄贰兼亭拯臭淘帛蚊熏谤叼数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,链栈的初始状态,藏蜗画订笨懦她池地乱盐冈抱崔吧仇樟珍椎碗玄移绑玛环灼觅白看露跋操数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,Sttus Topologiclsort(LGRPH G)indInDegree(G,indegree);MkeNUlLL(S);or(v=0;vn;+v)i(!indegreev)push(v,S);count=0;

31、while(!EMPTY(S)v=pop(S);print(v);+count;or(邻接于 v 的每个顶点 w)i(!(-indegreew)push(S,w);i(count n)cout“图中有环路”;else return OK;,算法一：应用栈,光毫泵洒疫田伸虐攘侩逻纠铰疥闲峡怨毒色亡搔旗颖重始冗椿蹲仅搬鳖盗数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,Sttus Topologiclsort(L)QUEUE Q;MkeNUlLL(Q);or(v=1;v=n;+v)i(indegreev=0)ENQUEUE(v,Q);nodes=0;while(!EMPT

32、Y(Q)v=RONT(Q);DEQUEUE(Q);cout v;nodes+;or(邻接于 v 的每个顶点 w)i(!(-indegreew)ENQUEUE(w,Q);i(nodes n)cout“图中有环路”;,算法二：应用队列,幽悦啥判韧杜持涟梨聪蝇篙粗奏长异斩匝鹤帐同草磋描埋唤梯妈逗酣诡乐数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,算法三：DS遍历生成拓扑序列,Void topods(v)PUSH(v,S);mrkv=TRUE;or(Lv 中的每一个顶点w)do i(mrkw=LSE)topods(w);print(top(S);POP(S);,Void d

33、s-topo(GRPH L)MKENULL(S);or(u=1;u=n;u+)mkeu=LSE;or(u=1;u=n;u+)i(!mrku)topods(u);,思想：借助栈，在DS中，把第一次遇到的顶点入栈，到达某一顶点递归返回时，从栈中弹出顶点并输出。,瀑碗斧智款苞罪伙挂叫召汲蛇舒舍媳恰狱指厌媳天矿纽法硬百跟辉墩碌吴数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,OE网（ctivity On Edge Network）在带权的有向图中，用结点表示事件，用边表示活动，边上权表示活动的开销（如持续时间），则称此有向图为边表示活动的网络,简称OE网。,*4.9 关键路径

34、,帽储谤另疤挛挫汐焙螟配掩毡咖岔概赊十粘伏蛋怕赶卓捎疙冻珠较仇坡纬数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,OE网的性质只有在某个顶点所代表的事件发生后，从该顶点出发的各有向边代表的活动才能开始;只有在进入某一顶点的各有向边代表的活动已经结束，该顶点所代表的事件才能发生；表示实际工程计划的OE网应该是无环的，并且存在唯一的入度为0的开始顶点（源点）和唯一的出度为0的结束点（汇点）。,恭烟弟讹承心段渴筏裂绕故唆兴戳篱懒窗梢贰久娃控邱摧室远丘亚喂唁替数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,OE网研究的主要问题：如果用OE 网表示一项

35、工程，那么仅仅考虑各个子工程之间的优先关系还不够，更多地是关心整个工程完成的最短时间是多少，哪些活动的延迟将影响整个工程进度,而加速这些活动能否提高整个工程的效率,因此OE网有待研究的问题是:(1)完成整个工程至少需要多少时间？(2)哪些活动是影响工程进度的关键活动？,常诸径线讶捣手豹基酵梭冶喂挤往忿绳泼砷皿瑶诵陈饭距拄靖泊逢倡哉怎数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,路径长度、关键路径、关键活动：路径长度：是指从源点到汇点路径上所有活动的持续时间之和。关键路径：在OE网中，由于有些活动可以并行，所以完成工程的最短时间是从源点到汇点的最大路径长度。因此，把从

36、源点到汇点具有最大长度的路径称为关键路径。一个OE中，关键路径可能不只一条。关键活动：关键路径上的活动称为关键活动。,刮沁班卵峦舍妨称肠舀旨慌章佛四只踌贺窝衡柑刘赡鳖肃别损怔复娃密楔数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,事件Vj 的最早可能发生时间VE(j)是从源点V1 到顶点Vj 的最长路径长度。活动i 的最早可能开始时间 E(k)设活动i 在边上,则E(i)也是从源点V1到顶点Vj 的最长路径长度。这是因为事件Vj发生表明以Vj为起点的所有活动i可以立即开始。因此,E(i)=VE(j).(1)事件Vk的最迟发生时间VL(k)是在保证汇点Vn在VE(n)时

37、刻完成的前提下，事件Vk的允许的最迟开始时间。在不推迟工期的情况下，一个事件 最迟发生时间VL(k)应该等于汇点的最早发生时间VE(n)减去从Vk到Vn的最大路径长度。,关键路径和关键活动性质分析：（与计算关键活动有关的量）,睦扰承芍媳倚夷握矫盯浆欠医吭馅钢闪考屋筒碧毖秩愁帘棘蚂团兔撵椽喜数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,活动i 的最迟允许开始时间 L(i)是指在不会引起工期延误的前提下，活动i允许的最迟开始时间。因为事件Vk发生表明以Vk为终点的入边所表示的所有活动均已完成，所以事件Vk的最迟发生时间VL(k)也是所有以Vk为终点的入边所表示的活动i可

38、以最迟完成时间。显然，为不推迟工期，活动i的最迟开始时间L(i)应该是i的最迟完成时间VL(k)减去i的持续时间，即 L(i)=VL(k)-CTjk.(2)其中,CTjk是活动i 的持续时间（上的权）。,关键路径和关键活动性质分析：（与计算关键活动有关的量）,纸乙姿厢牲尊博核钢蹿哗达娶牌跌缠黍胚浦腰寇眯叙嫁处怯装芋袱渣张柒数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,时间余量 L(i)-E(i)L(i)-E(i)表示活动 k 的最早可能开始时间和最迟允许开始时间的时间余量。关键路径上的活动都满足：L(i)=E(i).(3)L(i)=E(i)表示活动是没有时间余量的关

39、键活动。,关键路径和关键活动性质分析：（与计算关键活动有关的量）,由上述分析知，为找出关键活动，需要求各个活动的E(i)与 L(i)，以判别一个活动i是否 满足L(i)=E(i)。E(i)和L(i)可有公式(1)和(2)。而VE(k)和VL(k)可由拓扑分类算法得到。,利用拓扑分类算法求关键路径和关键活动,应复刨虞铜高荣拌唆户揭障诌卵沈炳碴辱色葱儿序侄毁隘护诚久翠刽的最数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,Step1(前进阶段)：从源点V1出发，令VE(1)=0，按拓扑序列次序求出其余各顶点事件的最早发生时间:,利用拓扑分类算法求关键路径和关键活动,其中T是

40、以顶点Vk为尾的所有边的头顶点的集合(2kn)如果网中有回路，不能求出关键路径则算法中止；否则转Step2。,其中S是以顶点Vj为头的所有边的尾顶点的集合(2jn-1),Step2(回退阶段)：从汇点Vn出发，令VL(n)=VE(n)，按逆拓扑有序求其余各顶点的最晚发生时间：,扯琼追底想悠抬沛框孟恰灾练肾叶娟柱襄商辱扁航躯搔沸暮有花舰胯却淘数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,Step3：求每一项活动i的最早开始时间:E(i)=VE(j)最晚开始时间:L(i)=VL(k)-CTjk 若某条边满足E(i)=L(i)，则它是关键活动。,利用拓扑分类算法求关键路径

41、和关键活动,为了简化算法,可以在求关键路径之前已经对各顶点实现拓扑排序,并按拓扑有序的顺序对各顶点重新进行了编号。不是任意一个关键活动的加速一定能使整个工程提前。想使整个工程提前，要考虑各个关键路径上所有关键活动。,莲陵混橱烘卖唾痔秦兔酮运抒累诧殿奏游尿文雷爱迸藉兵叮美芽羹醋刻胰数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,例1:,劲姥羹熄耍兜源捍碱怎赘病薛炊殿接仑蚊轰官箔瘪朴签柞遗抹瑟秩睡诱震数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,例2:,僳途瘤仲蔷疡钩禄芒钩柞芭洲里报萄凡而虾嫂锥写洪予制黍兼义锹诫墨切数据结构与算法基础(第三版)

42、第四章图数据结构与算法基础(第三版)第四章图,4.10 单源最短路径,20,Dijkstr算法基本思想：集合S的 初值为S=1D为各顶点当前最小路径从V-S中选择顶点w，使Dw的值最小 并将 w加入集合 S，则w的最短路径已 求出。调整其他各结点的当前最小路径 Dk=minDk,Dw+Cwk直到S中包含所有顶点,蜗杀萎吸扇姬相军糟巾土荧倔翠溯痢赠酣闭叹此向冯骗氦淋料慈妊洋饱积数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,算法的逐步求精过程：,算法：Void Dijkstr(G)S=1;or(i=2;i=n;i+)Di=C1i;or(i=1;in;i+)从V-S中选出

43、一个顶点w,使Dw最小；S=S+w;or(V-S中的每一个顶点v)Dv=min(Dv,Dw+Cwv);,让买慎灶线烷仓牧车垢握郴伟烬简拂滔辫慧凑仗摩余粟西祝钳笑徊惩器镊数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,算法：Void Dijkstr(GRPH G,costtype DMXVEX+1)int SMXVEX+1;or(i=1;i=n;i+)Di=G1j;Si=LSE;S 1=TRUE;or(i=1;in;i+)w=mincost(D,S);Sw=TRUE;or(v=2;v=n;n+)i(Sv!=TRUE)sum=Dw+Gwv;i(sum Dv)Dv=sum;

44、,int mincost(D,S)temp=ININITY;w=2;or(i=2;i=n;i+)i(!Si,撕妓两吕史帕荷睡执家莎今偶乾寡锁忍肛刚严培端沏宝湘签绕延仗援塘疮数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,例题,骂仓砰蔡瘁患雹咯骆蛊颖秸它芦泡祝重迁痊昌矣增乙肮晓邦霜奔孟诱基仗数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,*4.11 每一对顶点间的最短路径,基本思想：假设求顶点vi到顶点vj的最短路径。如果从 vi 到 vj 存在一条长度为Cij的路径，该路径不一定是最短路径，尚需进行 n 次试探。首先考虑路径(vi,v0,vj

45、)是否存在。如果存在，则比较(vi,vj)和(vi,v0,vj)的路径长度取长度较短者为从vi到vj的中间顶点的序号不大于0的最短路径。假设在路径上再增加一个顶点v1,也就是说，如果(vi,vj)和(v1,vj)分别是当前找到的中间顶点的序号不大于0的最短路径,那么(vi,v1,vj)就是有可能是从vi到vj的中间顶点的序号不大于1的最短路径。将它和已经得到的从vi到vj中间顶点序号不大于0的最短路径相比较，从中选出中间顶点的序号不大于1的最短路径，在增加一个顶点v2,继续进行试探。一般情况下，若(vi,vk)和(vk,vj)分别是从 vi到vk和从vk到Vj的中间顶点序号不大于 k-1 的最

46、短路径，则将(vi,vk,vj)和已经得到的从 vi到 vj且中间顶点序号不大于k-1的最短路径相比较，其长度较短者便是从vi到 vj 的中间顶点的序号不大于 k 的最短路径。,准恶阑章祝碳疲哉箭罗冯乔扬卵惋户峨音茹听畅是享易裙匹擒铣顽白腥僧数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,loyd算法:输入：表示有向图G=(V,E)的邻接矩阵C输出：表示任意两点之间最短路长的矩阵算法要点Void loyd(,C,n)or(i=1;i=n;i+)or(j=1;j=n;j+)ij=Cij;or(k=1;k=n;k+)or(i=1;i=n;i+)or(j=1;j=n;j+)

47、i(ik+kj ij)ij=ik+kj;,时间复杂度：O(n3),鳖傀准隐溯嚏有戌簇普县饵销嗜郴拐愧沃脑瞅个媚油搽推硫实运势福伤悠数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,求有向图的中心点：,定义：设G=(V,E)是一个有向图，dij表示从 I 到 j 的最短 距离。对任一点 k,称：,为结点k的偏心度，而称具有最小偏心度的结点为图G的中心点.,算法步骤：第一步：调用loyd算法，求每一对顶点间的最短路径矩阵D第二步：对矩阵D的每一列求最大值，即为各顶点j的偏心度。第三步：求具有最小偏心度的顶点k，即为中心点。,腊襟投褐尼襟酬尘芋蒜颐硬唇元渐圭癌咒挡残凋君窑倔剪甸洗皮函问蒋柑数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,图,沦隐心枫斜琵蚌姬眨咸运猪砒聋磊服婶藕睹缠躺召收懊雁慕捐啤圈麦盏淮数据结构与算法基础(第三版)第四章图数据结构与算法基础(第三版)第四章图,