页数：86页文件大小：665.5 KB来源： 数据结构ppt课件
本课件聚焦图的典型应用，从 AOE 网的关键活动与关键路径求法讲起，依次介绍无权最短路径、Dijkstra 正权最短路径与 Floyd 每对顶点最短路径算法，进而讲解最小支撑树的性质与 Prim、Kruskal 两种构造算法，最后介绍 Warshall 可及性算法与连通分量的求解。
第五章图5.1基本概念5.2图的存储结构5.3图的遍历5.4拓扑排序5.5关键路径5.6最短路径5.7最小支撑树5.8图的应用
25.5.1基本概念–边表示活动(Activity)–边的权值表示活动的持续时间(Duration)–顶点表示入边的活动已完成，出边的活动可以开始的状态，也称为事件(Event)这样的有向无环的带权图叫做AOE(Activity On Edges)网。
3[例]某工程源点：表示整个工程的开始（入度为零）。汇点：表示整个工程的结束（出度为零）。完成整个工程至少需要多少时间？为缩短工程的时间，应当加快哪些活动？325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点源点
从源点到各顶点的路径可能不止一条，路径长度也可能不同。只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径。路径长度：指路径上的各边权值之和。关键活动：关键路径上的活动。
325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点源点
5●关键活动有关的量：①事件vj的最早发生时间ve(j):从源点v0到vj的最长路径长度。②事件vj的最迟发生时间vl(j):保证汇点的最早发生时间不推迟的前提下，事件vj允许的最迟开始时间，等于ve(n-1)减去从vj到vn-1最长路径长度。325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点源点
ve(0)=0ve(1)= 6ve(2)= 4ve(3)= 5ve(4)= 7ve(5)= 7ve(6)= 16ve(7)= 14ve(8)= 18vl(8)= 18vl(7)= 14vl(6)= 16vl(5)= 10vl(4)= 7vl(3)= 8vl(2)= 6vl(1)= 6vl(0)= 0
7●关键活动有关的量：③活动ai的最早开始时间e(i):设活动ai在有向边< vj,vk>上,e(i)是从源点v0到vj的最长路径长度。因此e(i)=ve(j)。325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点源点
8●关键活动有关的量：④活动ai的最迟开始时间l(i):l(i)是在不会引起时间延误的前提下，该活动允许的最迟开始时间。设活动ai在有向边<vj,vk>上,则l(i)=vl(k)-weight(<j,k>)325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点源点
aie(i)l(i)0 0 0 6 4 5 7 7 716 140 2 3 6 6 8 7 71016 14a1a2a3a4a5a6a7a8a9a10a
10●关键活动：l(i)＝e(i)表示活动ak是没有时间余量的关键活动。325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点源点为找出关键活动,需要求各个活动的e(i)与l(i)，以判别是否l(i)＝e(i)为求得e(i)与l(i)，需要先求得从源点V0到各个顶点Vj的ve(j)和vl(j)。
求关键活动算法求关键活动的基本步骤：①对AOE网进行拓扑排序，按拓扑次序求出各顶点事件的最早发生时间ve，若网中有回路，则终止算法；②按拓扑序列的逆序求各顶点事件的最迟发生时间vl;③根据ve和vl的值，求各活动的最早开始时间e(i)与最迟开始时间l(i)，若e(i)=l(i)，则i是关键活动。
12[例]求关键活动––第1步ve(k)ve(0)＝0 k=0max{ve(j)+ weight(<j, k>)}<vj, vk>∈E(G), k=1, 2, …, n-1325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点源点按拓扑正序递推:
ve(0)=0ve(1)= ve(0)+weight(<0,1>)=0+6=6ve(2)= ve(0)+weight(<0,2>)=0+4=4ve(3)= ve(0)+weight(<0,3>)=0+5=5ve(4)= max{ve(1)+ weight(<1,4>)，ve(2)+ weight(<2,4>)}=max{6+1,4+1}=7ve(5)= ve(3)+weight(<3,5>)=5+2=7ve(6)= ve(4)+weight(<4,6>)=7+9=16ve(7)= max{ve(4)+ weight(<4,7>)，ve(5)+ weight(<5,7>)}=max{7+7,7+4}=14ve(8)= max{ve(6)+ weight(<6,8>)，ve(7)+ weight(<7,8>)}=max{16+2,14+4}=18
14[例]求关键活动––第2步vl(j)ve(n-1) j=n-1min{vl(k)-weight(<j, k>)}<vj, vk>∈E(G), j= n-2, n-3,…,0325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点源点按拓扑逆序递推:
vl(8)= ve(8)=18vl(7)= vl(8)-weight(<7,8>)=18-4=14vl(6)= vl(8)-weight(<6,8>)=18-2=16vl(5)= vl(7)-weight(<5,7>)=14-4=10vl(4)= min{vl(7)-weight(<4,7>)，vl(6)-weight(<4,6>)} =min{14-7,16-9}=7vl(3)= vl(5)-weight(<3,5>)=10-2=8vl(2)= vl(4)-weight(<2,4>)=7-1=6vl(1)= vl(4)-weight(<1,4>)=7-1=6vl(0)= min{vl(1)-weight(<0 ,1>)，vl(2)-weight(<0 ,2>),vl(3)-weight(<0 ,3>)} = min{6-6,6-4,8-5}=0
aie(i)l(i)li-ei0 0 0 6 4 5 7 7 716 140 2 3 6 6 8 7 71016 1402 302 300300a1a2a3a4a5a6a7a8a9a10a11[例]求关键活动––第3步：e(i)=ve(j), l(i)=vl(k)-weight(<j,k>)325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2汇点源点
算法CriticalPath()CPath1[计算事件的最早发生时间]FORi=1TOnDOve[i]←0.FORi=1TOn–1DO(p←adjacent(Head[i]).WHILEpDO(k←VerAdj(p).IF(ve[i]+cost(p)>ve[k])THENve[k]←ve[i]+cost(p).p←link(p)))
CPath2[计算事件的最迟发生时间]FORi= 1 TOnDOvl[i]←ve[n] .FORi=n–1 TO 1 STEP–1 DO(p←adjacent (Head[i]) .WHILEpDO(k←VerAdj(p) .IF (vl[k]–cost(p) <vl[i] ) THENvl[i]←vl[k]–cost(p) .p←link(p)))
CPath3[求诸活动的最早开始时间和最迟开始时间]FORi=1TOnDO(p←adjacent(Head[i]).WHILEpDO(k←VerAdj(p).e←ve[i].l←vl[k]–cost(p).IFl=eTHENPRINT"<i,k>isCriticalActivity!"p←link(p)))▐
时间复杂性：对定点进行拓扑排序的时间复杂性为O(n+e),以拓扑排序求ve[i]和以拓扑逆序求vl[i]时,所需时间为均为O(e),求各个活动的e[k]和l[k]的时间复杂度为O(e),整个算法的时间复杂性是O(n+e)。
第五章图5.1基本概念5.2图的存储结构5.3图的遍历5.4拓扑排序5.5关键路径5.6最短路径5.7最小支撑树5.8图的应用
225.6最短路径问题两顶点间可能存在多条路径，每条路径经过的边数不同，每条路径的各边权值之和也不同。从一个指定的顶点到达另一指定顶点的路径上各边权值之和最小的路径被称为最短路径，这类问题亦称为最短路径问题。
单源(由一个指定顶点到其他顶点)最短路径无权最短路径正权最短路径负权最短路径每对顶点之间的最短路径问题
245.6.1无权最短路径问题无权——所有边的权值都为1源点到各顶点的路径所经历的边的数目就是路径的长度相对于源点由近及远依次求各顶点的最短路径
算法思想：设Di为源点S到顶点i的最短路径长度①访问初始顶点S，即令DS=0。②从S出发，找最短路径为1的顶点，即S的所有邻接顶点w，令Dw=DS+1③从上步访问的顶点w出发，找最短路径为2的顶点，即w未被访问的邻接顶点v，令Dv=Dw+1④继续上述过程，直至处理完所有顶点。1V12V63V51V32V43V20SV
26[例]V1V6V5V3V4V21122330SV
上述过程中，访问顶点的次序与对图进行广度优先遍历的次序是一致的;初始时，令Dw=-1，当Dw由-1变成一个正整数时，表示从源点到w的最短路径已求完，Dw值就是最短路径长度,实现时使用数组dist[]存储;为了找到最短路径，使用path[]存储从源点到顶点i的最短路径上最后一个经历的顶点。
算法ShortestPath(v,n)SPath1[初始化]CREATQ(Q).FORi=1TOnDO(path[i]←-1.dist[i]←-1.)dist[v]←0.Q←v.
SPath2[求从顶点v到其他各顶点的最短路径]WHILENOT(ISEMTQ(Q))DO(u←Q.p←adjacent(Head[u]).WHILEp≠ DO(k←VerAdj(p).IF(dist[k]=-1)THEN(Q←k.//将u的未访问的邻接顶点入队dist[k]←dist[u]+1.//修改其path[]值和dist[]值path[k]←u)p←link(p).))▐1V12V63V51V32V43V20SV
在最短路径的计算中，一个顶点入队出队各一次，时间复杂性为O(n)，而对每个顶点，都要对它的边链表进行遍历，其遍历邻接表的开销为O(e)，于是整个算法的时间复杂性为O(n+e)。
315.6.2正权最短路径问题给定一个带权图D与源点v，求从v到D中其它顶点的最短路径,限定各边的权值为正实数。正权最短路径问题不能采用无权最短路径算法。v0v1v2283
Dijkstra算法思想按路径长度非递减的次序，逐步产生最短路径的算法，解决正权单源最短路径问题。首先求出从源点v出发，长度最短的一条最短路径；再参照它求出长度次短的一条最短路径；依此类推，直到求出从顶点v到其它各顶点的最短路径为止。
把图中所有顶点分成两组，第一组：已求完最短路径的顶点；第二组：未求完最短路径的顶点。按最短路径长度递增的顺序逐个把第二组的顶点加到第一组中。为了求最短路径，引入辅助数组dist，dist[i]表示当前找到的源点v0到vi的最短路径长度。初始时：S={}，dist[0]=0，dist[i]=+SV-S
设S是已求得最短路径的顶点集合，则：下一条最短路径必然是从源点v0出发，中间只经过S中的顶点便可到达的那些顶点vx(vx∈V-S)的路径中的一条。每次求最短路径，也就是在V-S中找具有最小dist值的顶点vk，将vk加入集合S，然后对vi∈V-S，修改dist[i]值。经第一次操作，S={v0}，若从源点v0到vi有边，则dist[i]为该边上的权值；
若从v0到vi无边，则dist[i]仍为+。SV-S
Dijkstra算法描述初始时（S为初始顶点）,Ds=0且i≠S，有Di=＋∞。①在未访问顶点中选择Dv最小的顶点v，访问v，令S[v]=1。②依次考察v的邻接顶点w，若Dv+weight(<v,w>)<Dw，则改变Dw的值，使Dw=Dv+weight(<v,w>)。③重复①②，直至所有顶点被访问。
为了找到最短路径，使用path[]存储从S到i的最短路径上最后一个经历的顶点。
36[例]132581020453012023401234024310∧5134∧3038∧225410∧02024412∧
spathdist0000003421∞∞∞0∞1325810204530120234①在未访问顶点中选择Dv最小的顶点v，访问v，令S[v]=1。②依次考察v的邻接顶点w，若Dv+weight(<v,w>)<Dw，则改变Dw的值，使Dw=Dv+weight(<v,w>)。③重复①②，直至所有顶点被访问。
38013302343∞∞1325810204530120234spathdist1000003421030∞3∞v0v
spathdist100010342103028311v0v0v1v13258133002343028111325810204530120234
4003421spathdist1100103028311v0v1v1v0132581020453012023431204158132342311
4103421spathdist1100102315311v0v3v1v3132581020453012023431204158132342311
42120415813234231131325810204530120234spathdist1100102315311v0v3v1v
spathdist111110342102315311v0v3v1v3Dijkstra算法:按照非递减顺序依次得到各顶点的最小路径长度。120415813234231131325810204530120234
定理5.4Dijkstra算法可以按照非递减次序依次得到各顶点的最小路径长度。证明：归纳法算法得到的路径值是各顶点的最小路径长度。算法得到的路径值是按非递减次序得到的。
算法DShortestPath(n, v)DSPath1[初始化]FORi= 1 TOnDO(path[i]←-1.dist[i]←max.s[i]←0. )//数组s[i]记录i是否被访问过dist[v]←0.s[v]←1.p←adjacent (Head[v]) .u←v.
DSPath2[求从初始顶点v到其他各顶点的最短路径]FORj=1TOn-1DO//求从v到其他各顶点的最短路径(WHILEp≠ DO//修改u邻接顶点的path[]值和dist[]值(k←VerAdj(p).IF(s[k]≠1ANDdist[u]+cost(p)<dist[k])THEN(dist[k]←dist[u]+cost(p).path[k]←u.)p←link(p))//确定即将被访问的顶点uldist←max.FORi=1TOnDOIF(dist[i]>0ANDdist[i]<ldistANDs[i]=0)THEN(ldist←dist[i].u←i.)s[u]←1.//访问up←adjacent(Head[u]))▐//p为u的边链表的头指针该算法的时间复杂性为O(n2+e)，也可认为是O(n2)
475.6.3每对顶点间的最短路径问题：已知一个各边权值均大于0的带权有向图，对每一对顶点vi≠vj，求vi与vj间的最短路径和最短路径长度。可依次把每个顶点作为源点，执行n次Dijkstra算法。Floyd算法：定义一个n阶方阵序列：A(-1),A(0), …,A(n-1).
Floyd算法的基本思想：设邻接矩阵存储图，定义初始矩阵A(-1)[i][j]=Edge[i][j]；1、求A(0),即从vi到vj经由顶点可以是{v0}的最短路径长度；2、求A(1),即从vi到vj经由顶点可以是{v0,v1}的最短路径长度；…n、求A(n-1),即从vi到vj经由顶点可以是{v0,v1,…,vn-1}的最短路径长度；
其中A(k)[i][j]=min{A(k-1)[i][j]，A(k-1)[i][k]+A(k-1)[k][j]},k=0,1,…,n-1
从A(3)知，顶点1到0的最短路径长度为a[1][0]=11,其最短路径path[1][0]=2，path[1][2]=3，path[1][3]=1,表示顶点0←顶点2←顶点3←顶点1;从顶点1到顶点0最短路径为<1,3>,<3,2>,<2,0>。
算法AllLength(n)ALength1[初始化]FORi=0TOn-1DO//矩阵A和path初始化FORj=0TOn-1DO(A[i][j]←edge[i][j].//初始化的A即A(-1)IF(i≠jANDA[i][j]<max)THENpath[i][j]←i.ELSEpath[i][j]←-1.)
ALength2[求图中任意两顶点的最短路径]FORk=0TOn-1DO//从A(-1)开始针对每个k逐步构造A(n-1)FORi=0TOn-1DOIF(i≠k)THENFORj=0TOn-1DOIF(j≠kANDj≠iANDA[i][k]<maxANDA[k][j]<maxANDA[i][k]+A[k][j]<A[i][j])THEN(A[i][j]←A[i][k]+A[k][j].path[i][j]←path[k][j].)▐
Floyd算法的时间复杂度为O(n3)，与调用n次Dijkstra算法求每对顶点的最短路径的时间复杂度相同。但Dijkstra算法仅针对正权图，而Floyd算法允许图中有带负权值的边，但不许有包含带负权值的边组成的回路；且Floyd算法更简单易于理解。
本章给出的求解最短路径的算法，不仅适用于带权有向图，对带权无向图也可以适用。因为带权无向图可以看作是有往返二重边的有向图。
第五章图5.1基本概念5.2图的存储结构5.3图的遍历5.4拓扑排序5.5关键路径5.6最短路径5.7最小支撑树5.8图的应用
565.7最小支撑树1、基本概念2、生成最小支撑树算法Prim算法Kruskar算法
最小支撑树——基本概念对于一个无向网络——无向加权连通图N=(V,E,C)(C表示该图为权图)，其顶点个数为|V|=n，图中边的个数为|E|，我们可以从它的|E|条边中选出n-1条边，使之满足（1）这n-1条边和图的n个顶点构成一个连通图。（2）该连通图的代价是所有满足条件(1)的连通图的代价的最小值。
这样的连通图被称为网络的最小支撑树(Minimum-costSpanningTree)。
最小支撑树的性质最小支撑树中没有回路——若MST的边集中有回路，显然可通过去掉回路中某条边而得到花销更小的MST最小支撑树是一棵有|V|-1条边的树最小支撑树的边集支撑起了图中所有顶点，且边集的代价最小最小支撑树的应用使连接电路板上一系列接头所需焊接的线路最短在n个城市间建立造价最低的通讯网络
595.7最小支撑树1、基本概念2、生成最小支撑树算法Prim算法Kruskar算法
MST性质：N=(V,E,C)是一个连通网，U是V的一个非空子集，若u,v满足weight(u,v)=min{weight(u0,v0)|u0∈U,v0∈V-U}则必存在N的一棵最小支撑树，该支撑树中包括边(u,v)。UV-Uuv
611、普里姆(Prim)算法(逐点加入)设N=(V,E,C)为连通网，TE是N的最小支撑树MST的边的集合，U为MST顶点集。①U={uo}(uo∈V),TE=Φ；②找到满足weight(u,v)＝min{weight(u1,v1)|u1∈U,v1∈V-U},的边，把它并入TE，同时v并入U；③反复执行②,直至V=U,算法结束。
624316504535562217UV-U[例]43165045355622170214316504535562217
634316504535562217UV-U40215021
644053221402154316504535562217UV-U
654105352214316504535562217UV-U4053221
66410535221UV-U431650453556221743104535221
假设用邻接矩阵存储图。普里姆算法的实现需要增设两个辅助数组closedge[n]和TE[n-1].closedge[n]的每个数组元素由两个域构成：Lowcost和Vex，其定义如下：如果，则=而closedge[v].Vex存储的是该边依附在U中的顶点u.如果，则数组TE[n-1]是最小支撑树的边集合，每个数组元素TE[i]表示一条边，TE[i]由三个域head、tail和cost构成，它们分别存放边的始点、终点和权值。
68432156452314326515645562317131413164164231421645231
694326515645562317V-UU654321Vclosedge{2 ,3 ,4 ,5,6}{1}1max1max151116-10VexLowcost4326515645562317UV-UPrim:FORi= 1 TOnDO(Lowcost(closedge[i])←edge[1][i] .Vex(closedge[i])←1)Vex(closedge[1])←-1.count←1.
V-UU654321Vclosedge{2 ,3 ,4 ,5 ,6}{1}1max1max151116-10VexLowcostv←0.//求当前权值最小的边和该边的终点vmin←max.FORj=1TOnDOIF(vex(closedge[j])≠-1ANDLowcost(closedge[j])<min)(v←j.min←Lowcost(closedge[j]))
V-UU654321Vclosedge{2, 4 ,5 ,6}{1,3}1max1max15-1016-10VexLowcostIfv≠0THEN//v加入U中(head(TE[count])←Vex(closedge[v]) .tail(TE[count])←v.cost(TE[count])←Lowcost(closedge[v]).count←count +1.//计数器加1Lowcost(closedge[v])←0.
V-UU654321Vclosedge{2,4 ,5,6 }{1,3}343515-1035-10VexLowcost4326515645562317UV-UFORj= 1 TOnDO//修改某些顶点的值IF(Vex(closedge[j])≠-1 ANDedge[v][j] <Lowcost(closedge[j])) THEN(Lowcost(closedge[j])←edge[v][j] .Vex(closedge[j])←v. ))) )
算法Prim()Prim1[初始化邻接矩阵]FORi=1TOnDOFORj=1TOnDOIF(edge[i][j]=0)edge[i][j]=max;//max是预定义常数Prim2[以顶点1为初始顶点，初始化数组closedge[]FORi=1TOnDO(Lowcost(closedge[i])←edge[1][i].Vex(closedge[i])←1)Vex(closedge[1])←-1.//顶点1进入集合Ucount←1.//支撑树的边记数器count
Prim3[构造图的最小支撑树]FORi=2 TOnDO//循环n-1次(v←0.min←max.//求当前权值最小的边和该边的终点vFORj= 1 TOnDOIF (vex(closedge[j])≠-1 ANDLowcost(closedge[j]) <min) THEN(v←j.min←Lowcost(closedge[j]) . )IFv≠0THEN//将该边加入TE中，点v加入集合U中(head(TE[count])←Vex(closedge[v]) .tail(TE[count])←v.cost(TE[count])←Lowcost(closedge[v]).count←count +1.//计数器加1Lowcost(closedge[v])←0.//修改域值Vex(closedge[v])←-1.//顶点v进入集合U//修改v的邻接顶点的closedge值FORj= 1 TOnDOIF(Vex(closedge[j])≠-1 ANDedge[v][j] <Lowcost(closedge[j]))THEN(Lowcost(closedge[j])←edge[v][j] .Vex(closedge[j])←v. )) )▐普里姆算法的时间复杂度为O(n2)，适用于求边稠密网的最小支撑树。
752、克鲁斯卡尔(Kruskar)算法（逐边加入）设连通网N=(V,E,C)，T为N的最小支撑树。初始时T={V,Φ}，即T中没有边，只有n个顶点，也就是n个连通分量。①在E中选择权值最小的边，并将此边从E中删除。②如果此边的两个顶点在T的不同的连通分量中，则将此边加入到T中，从而导致T中减少一个连通分量;如果此边的两个顶点在同一连通分量中，则重复执行①②，直至T中仅剩一个连通分量时，终止操作。
76[例]1104532104532123104532210431453221431045352214316504535562217
普里姆(Prim)算法的时间复杂性为O(n2)，算法适用于求边稠密网的最小支撑树。克鲁斯卡尔(Kruskar)算法正好相反，它适用于求边稀疏网的最小支撑树，它的时间复杂性为O(eloge).
第五章图5.1基本概念5.2图的存储结构5.3图的遍历5.4拓扑排序5.5关键路径5.6最短路径5.7最小支撑树5.8图的应用
795.8图的应用1、可及性与Warshall算法2、连通分量
801、可及性与Warshall算法图G中的两个顶点vi和vj，若从vi到vj存在一条有向路径，则称vi到vj可及。用n×n阶可及矩阵R来描述顶点之间的可及关系，可及矩阵R的定义如下：若vi到vj可及，则Rij=1，否则Rij=0.
可及的传递性：如果vi至vj可及, vj至vk可及,那么必有vi至vk可及。由图G的顶点集V、边集E，以及新添加的虚边（表示顶点可及）构成原图G的扩展图，也称图G的传递闭包。DBCA11 1 101 0 101 1 100 0 1可及矩阵
根据可及的传递性，在可及矩阵中，若Rik=1且Rkj=1，则必有Rij=1.基于此思想，StephenWarshall在1962年提出了著名的Warshall算法，用来求有向图G的可及矩阵。
Warshall算法与Floy算法类似，是一个动态规划过程，递推公式为：其中，WSM0=A，WSM(k)[i][j]表示顶点i只经过顶点1，2，…，k到达j的可及性。
852、连通分量有向图有三个连通分量，它们各自包含的顶点是：A B CDE F设计一个算法，求图的所有连通分量。FEDCBA
本章作业173页：5-1、5-7、5-12、5-13、5-14、5-15、5-16
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}