数据结构课件有向无环图2009级

§7.5有向图及应用数据结构离散数学编译原理程序语言数字逻辑操作系统数据库软件工程计算机组成汇编网络计算机导论课程流程§7.5有向图及应用§7.5有向图及应用例：某工程可分为7个子工程，工程流程图工程流程V4V3V2V6V5V1V7AOV网(activityonvertexnet)

以顶点表示活动，以有向边表示活动之间的优先关系的有向图。工程问题工程流程图是否合理(无回路)安排施工计划完成整个工程至少需要多少时间(AOE网)哪些子工程是关键子工程(AOE网)

拓扑排序V4V3V2V6V5V1V7V4V3V2V6V5V1V77.5.1拓扑排序

例施工计划V1V2V3V4V5V6V7拓扑排序：把AOV网中各顶点按照它们相互之间的优先关系排列成一个线性序列。拓扑序列：满足AOV网的优先关系的顶点序列。

V1V2V3V4V5V6V7拓扑序列V4V3V2V6V5V1V7

V2V1V3V4V5V6V7

V2V1V4V3V5V6V77.5.1拓扑排序1）在有向图中选一无前趋的顶点v，输出；

2）从有向图中删除v及以v为尾的孤；

3）重复1)、2)直接全部输出全部顶点或有向图中不存在无前趋顶点；拓扑排序基本步骤V4V3V2V6V5V1V77.5.1拓扑排序V4V3V2V6V5V1V7

输出：V1例17.5.1拓扑排序V4V3V2V6V5V1V7

输出：V1例17.5.1拓扑排序V4V3V2V6V5V7

输出：V1V2例17.5.1拓扑排序V4V3V2V6V5V7

输出：V1V2例17.5.1拓扑排序V4V3V6V5V7

输出：V1V2V4例17.5.1拓扑排序V4V3V6V5V7

输出：V1V2V4例17.5.1拓扑排序V3V6V5V7

输出：V1V2V4V3例17.5.1拓扑排序V3V6V5V7

输出：V1V2V4V3例17.5.1拓扑排序V6V5V7

输出：V1V2V4V3V5例17.5.1拓扑排序V6V5V7

输出：V1V2V4V3V5例17.5.1拓扑排序V6V7

输出：V1V2V4V3V5V6例17.5.1拓扑排序V6V7

输出：V1V2V4V3V5V6例17.5.1拓扑排序V7

输出：V1V2V4V3V5V6V7例17.5.1拓扑排序

拓扑序列：V1V2V4V3V5V6V7V4V3V2V6V5V1V7例17.5.1拓扑排序

输出：V1V3V2V5V4V1例27.5.1拓扑排序

输出：V1V3V2V5V4V1例27.5.1拓扑排序

输出：V1V2V3V2V5V4例27.5.1拓扑排序

输出：V1V2V3V2V5V4没有无前驱的顶点拓扑排序失败例2拓扑排序算法

输入数据：图结果数据：图的拓扑序列V4V3V2V6V5V1V71）在有向图中选一无前驱的顶点v，输出；

2）从有向图中删除v及以v为尾的孤；

3）重复1)、2)直接全部输出全部顶点或有向图中不存在无前趋顶点；拓扑排序基本步骤

1）在有向图中选一入度为0的顶点v，输出；

2）将顶点v邻接到的所有顶点的入度减1；V4V3V2V6V5V1V7拓扑排序算法

存储结构图：邻接表图的拓扑序列：直接输出V4V3V2V6V5V1V7G.vexs

V1V2V3V4V5V6V701234562456334556拓扑排序算法辅助数数据结构入度数组0012232indegree栈：存储入度为零的顶点(位置）01S.baseV4V3V2V6V5V1V7拓扑排序算法0012232indegree01S.base0011132indegree0S.base输出V2V4V3V2V6V5V1V7G.vexs

V1V2V3V4V5V6V701234562456334556StatusTopoSort(ALGraphG){/*有向图用邻接表G存储,若拓扑排序成功，输出拓扑序列返回OK，否则返回ERROR*/FindInDegree(G,indegree);//求各顶点入度

InitStack(S);count=0;//计数器：对放入拓扑序列的顶点计数

for(i=0;i<G.vexnum;++i)//0入度顶点进栈Sif(indegree[i]==0)Push(S,i); 01S.topS.base0012232indegreewhile(!EmptyStack(S)){Pop(S,v);//从栈顶取一入度为零的顶点vPrint(v);//输出v++count;

for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,j,v))

if(--indegree[w]==0)Push(S,w);}//while

DestroyStack(S);if(count<G.vexnum)returnERROR;elsereturnOK;}将顶点v邻接到的顶点w的入度减1，若入度减为0，则w入栈

7.5.2关键路径对工程人们关心另一类问题：完成整个工程至少需要多少时间？哪些子工程是影响工程进度的关键子工程？7.5.2关键路径AOE网(activityonedgenet) AOE网是有一个带权的有向无环图。边表示活动，顶点表示事件，权值表示活动持续的时间。事件活动a1=3a2=2a6=3a5=4a3=2a7=2a8=1V3V1V4V6V5V2a4=3源点、汇点网中入度为零的顶点，称为源点；网中出度为零的顶点，称为汇点。7.5.2关键路径a1=3a2=2a6=3a5=4a3=2a7=2a8=1V3V1V4V6V5V2a4=37.5.2关键路径(顶点)事件发生以该顶点为终点的所有活动都已经结束；以该顶点起点所有活动可以开始；a1=3a2=2a6=3a5=4a3=2a7=2a8=1V3V1V4V6V5V2a4=3事件7.5.2关键路径AOV网和AOE网的区别都能用来表示工程中的各子工程的流程AOV网用顶点表示活动AOE网用边表示活动AOV网侧重表示活动的前后次序，AOE网除表示活动先后次序，还表示了活动的持续时间等;可利用AOE网解决工程所需最短时间及哪些子工程拖延会影响整个工程按时完成等问题;7.5.2关键路径关键路径从源点到汇点之间的最长路径关键路径长度就是为完成整个工程所需要的最短时间。例完成整个工程至少需要时间：

8天源点汇点a1=3a2=2a6=3a5=4a3=2a7=2a8=1V3V1V4V6V5V2a4=3关键活动关键路径上的活动是关键活动关键活动拖延（弧上的权值增加）会使完成该工程的时间拖延。7.5.2关键路径例源点汇点a1=3a2=2a6=3a5=4a3=2a7=2a8=1V3V1V4V6V5V2a4=3关键活动和工期(关键路径长度)求解a1=3a2=2a6=3a5=4a3=2a7=2a8=1V3V1V4V6V5V2a4=3关键活动和工期(关键路径长度)求解事件vj的最早发生时间ve[j]事件vj的最迟发生时间vl[j]活动ak的最早开始时间ee[k]活动ak的最迟开始时间el[k]a1=3a2=2a6=3a5=4a3=2a7=2a8=1V3V1V4V6V5V2a4=3事件vj的最早发生时间ve[j]以该事件为终点的所有活动都结束的最早时间计算方法

ve[1]=0ve[j]=max{ve(i)+dut(<i,j>)}ij

a1=3a2=2a6=3a5=4a3=2a7=2a8=1V3V1V4V6V5V2a4=3ve[1]=0ve[3]=max{ve(1)+dut(<1,3>)}=0+2=2ve[2]=max{ve(1)+dut(<1,2>)}=0+3=3ve[4]=max{ve(2)+dut(<2,4>),ve(3)+dut(<3,4>)}=max{3+2,2+4}=6事件vj的最早发生时间ve[j]a1=3a2=2a6=3a5=4a3=2a7=2a8=1V3V1V4V6V5V2a4=3事件Vj

最早发生

最晚发生时间ve[j]时间vl[j]V1V2V3V4V5V6032668事件vi的最迟发生时间vl[i]在不推迟整个工程完成时间的前提下,该事件最迟必须发生的时间。

计算方法

vl[n]=ve[n]vl[i]=min{vl(j)-dut(<i,j>)}

j

i

a1=3a2=2a6=3a5=4a3=2a7=2a8=1V3V1V4V6V5V2a4=3vl[6]=8vl[3]=min{vl(4)-dut(<3,4>),vl(6)-dut(<3,6>)}=min{6-4,8-3}=2vl[4]=min{vl(6)-dut(<4,6>)}=8-2=6事件vi的最迟发生时间vl[i]a1=3a2=2a6=3a5=4a3=2a7=2a8=1V3V1V4V6V5V2a4=3事件Vj

最早发生

最晚发生时间ve[j]时间vl[j]

V1V2V3V4V5V6032668042678

活动ak=<ij>的最早开始时间ee[k]该活动的起点事件的最早发生时间计算方法

ee[k]=ve[i]

i

jaka1=3a2=2a6=3a5=4a3=2a7=2a8=1V3V1V4V6V5V2a4=3ee[1]=ee[2]=ve[1]=0ee[3]=ee[4]=ve[2]=3

活动ak=<ij>的最早开始时间ee[k]a1=3a2=2a6=3a5=4a3=2a7=2a8=1V3V1V4V6V5V2a4=3a1(1-2)a2(1-3)a3(2-4)a4(2-5)a5(3-4)a6(3-6)a7(4-6)a8(5-6)

活动ee[k]el[k]00332266活动ak=<ij>的最迟开始时间e1[k]在不推迟整个工程完成时间的前提下,该活动最迟必须开始的时间。计算方法

e1[k]=vl[j]-dut(<i,j>)

i

jaka1=3a2=2a6=3a5=4a3=2a7=2a8=1V3V1V4V6V5V2a4=3el[7]=vl[6]-dut(<4,6>)=8-2=6el[5]=vl[4]-dut(<3,4>)=6-4=2活动ak=<ij>的最迟开始时间e1[k]a1=3a2=2a6=3a5=4a3=2a7=2a8=1V3V1V4V6V5V2a4=3a1(1-2)a2(1-3)a3(2-4)a4(2-5)a5(3-4)a6(3-6)a7(4-6)a8(5-6)

活动ee[k]el[k]0033226610442567事件Vj

最早发生

最晚发生时间ve[j