有向无环图及其应用.ppt

7.1图的定义和术语￡7.5有向无环图及其应用（2）表达式子式共享￡7.5.2拓扑排序例如，一个软件专业的学生必须学习一系列基本课程(如图7.18所示)，
其中有些课程是基础课，它独力于其他课程，如《高等数学》；而另一些
课程必须在学完作为它的基础的先修课程才能开始。如，在《程序设计基
础》和《离散数学》学完之前就不能开始学习《数据结构》。这些先决条
件定义了课程之间的领先（优先）关系。这个关系可以用有向图7.19清楚
的表示。（3）拓扑排序 count=0;
while(!StackEmpty(S)){
Pop(S,i);
printf(i,G.vertices[i].data); //输出i号顶点并计数
++count;
for(p=G.vertices[i].firstarc;p;p=p－>nextarc){
k=p－>adjvex; //对i号顶点的每个邻接点的入度减1
if(!(――indegree[k]))
Push(S,k); //若入度减为0，则入栈
}//for
}//while
if(count<G.vexnum)
returnERROR; //该有向图有回路
}//TopologicalSort③例子
以图7.20(a)中的有向图为例。￡7.5.3关键路径例如，通常，AOE-网可用来估算工程的完成时间。图7.21是一个假想的
有11项活动的AOE-网。其中有9个事件v1,v2,v3,…,v9，每个事件表示在它
之前的活动已经完成，在它之后的活动可以开始。与每个活动相联系的数是
执行该活动所需的时间。②从vl(n－1)=ve(n－1)起向后递推
vl(i)=Min{vl(j)－dut(<i,j>)} <i,j>∈S,i=n－2,…,0
其中，S是所有以第i个顶点为尾的弧的集合。①算法思想：
1．输入e条弧<j,k>，建立AOE-网的存储结构；
2．从源点v0出发，令ve[0]=0，按拓扑有序求其余各顶点的最早发
生时间ve[i](1≤i≤n－1)。如果得到的拓扑有序序列中顶点个数小于网中
顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步
骤3。
3．从汇点vn出发令vl[n－1]=ve[n－1]，按逆拓扑有序求其余各顶
点的最迟发生时间veli](2≤i≤n－2)；
4．根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开
始时间l(s)。若某条弧满足条件e(s)=l(s)，则为关键活动。StatusTopologicalOrder(ALGraphG,Stack&T){
//有向网G采用邻接表存储结构，求各顶点事件最早发生时间ve
//（全局变量）。T为拓扑序列顶点栈，S为零入度顶点栈。
//若G无回路，则用栈T返回G的一个拓扑序列，且函数值为OK，
//否则ERROR。
FindInDegree(G,indegree); //对各顶点求入度indegree[0..vernum-1]
建0入度顶点栈S;
InitStack(T); //初始化
count=0;
ve[0..G.vexnum－1]=0;
while(!StackEmpty(S)){
Pop(S,j);
Push(T,j); //j号顶点入T栈并计数
++count;
for(p=G.vertices[i].firstarc;p;p=p－>nextarc){
k=p－>adjvex; //对j号顶点的每个邻接点的入度减1
if((――indegree[k])==0)
Push(S,k); //若入度减为0，则入栈 if(ve[j]+*(p－>info)>ve[k])
ve[k]=ve[j]+*(p－>info);
}//for*(p－>info)=dut(<j,k>)
}//while
if(count<G.vexnum)
returnERROR; //该有向网有回路
}//TopologicalOrder while(!StackEmpty(T)) //按拓扑逆序求各顶点的vl值
for(Pop(T,j),p=G.vertices[i].firstarc;p;p=p－>nextarc){
k=p－>adjvex;
dut=*(p－>info); //dut<j,k>
if(vl[k]－dut<vl[j])
vl[j]=vl[k]－dut;
}//for
for(j=0;j<G.vexnum;++j) //求ee，el和关键活动
for(p=G.vertices[j].firstarc;p;p=p－>nextarc){
k=p－>adjvex;
dut=*(p－>in