详解图的应用（最小生成树、拓扑排序、关键路径、最短路径）

for(i=0；i<G.vexnum； ++i) if(!indegree[i])Push(S，i) //建零入度顶点栈,s入度为0者进栈

InitStack(T)； count=0；ve[0..G.vexnum-1]=0； //初始化 while(!StackEmpty(S)){ //j号顶点入T栈并计数

Pop(S，j)； Push(T，j)；++count; for(p=G.vertices[j].firstarc；p；p=p->nextarc){

k=p—>adjvex； //对i号顶点的每个邻接点的入度减l 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) return ERROR； //该有向网有回路

else return OK；

}//TopologicalOrder

Status CriticalPath (ALGraph G){ //G为有向网，输出G的各项关键活动。

if(!TopologicalOrder(G，T)) return ERROR； //初始化顶点事件的最迟发生时间 vl[0..G.vexnum-1]=ve[0..C.vexnum-1]； //按拓扑逆序求各顶点的vl值

while(!StackEmpty(T)) for( Pop(T, j), p=G.vertices[j].firstarc；p； p=p->nextarc){

k=p->adjvex； dut=*(p—>info)； //dut<i，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]；p；p=p->nextarc){

k=p->adjvex； dut=*(p—>info)；ee=ve[j]；el=v1[k]-dut；tag = (ee==e1) ? ‘*' ： ‘'； printf(j，k，dut，ee，el，tag)； //输出关键活动

} }//CriticalPath ?

图(a)所示网的关键路径：可见a2、a5和a7为关键活动，组成一条从源点到汇点的关键路径，如图(b)所示。