// algo7-5.cpp 求關(guān)鍵路徑。實(shí)現(xiàn)算法7.13、7.14的程序
 #include"c1.h"
 #define MAX_NAME 5 // 頂點(diǎn)字符串的最大長(zhǎng)度+1
 typedef int InfoType;
 typedef char VertexType[MAX_NAME]; // 字符串類型
 #include"c7-2.h"
 #include"bo7-2.cpp"

 int ve[MAX_VERTEX_NUM]; // 全局變量(用于算法7.13和算法7.14)

 void FindInDegree(ALGraph G,int indegree[])
 { // 求頂點(diǎn)的入度，算法7.12、7.13調(diào)用
   int i;
   ArcNode *p;
   for(i=0;i<G.vexnum;i++)
     indegree[i]=0; // 賦初值
   for(i=0;i<G.vexnum;i++)
   {
     p=G.vertices[i].firstarc;
     while(p)
     {
       indegree[p->adjvex]++;
       p=p->nextarc;
     }
   }
 }

 typedef int SElemType; // 棧類型
 #include"c3-1.h"
 #include"bo3-1.cpp"
 Status TopologicalOrder(ALGraph G,SqStack &T)
 { // 算法7.13  有向網(wǎng)G采用鄰接表存儲(chǔ)結(jié)構(gòu),求各頂點(diǎn)事件的最早發(fā)生時(shí)間ve
   // (全局變量)。T為拓?fù)湫蛄许旤c(diǎn)棧,S為零入度頂點(diǎn)棧。若G無(wú)回路,則用棧T
   // 返回G的一個(gè)拓?fù)湫蛄?且函數(shù)值為OK,否則為ERROR
   int j,k,count,indegree[MAX_VERTEX_NUM];
   SqStack S;
   ArcNode *p;
   FindInDegree(G,indegree);//對(duì)各頂點(diǎn)求入度indegree[0..vernum-1]
   InitStack(S); // 初始化棧
   for(j=0;j<G.vexnum;++j) // 建零入度頂點(diǎn)棧S
     if(!indegree[j])
       Push(S,j); // 入度為0者進(jìn)棧
   InitStack(T); // 初始化拓?fù)湫蛄许旤c(diǎn)棧
   count=0; // 對(duì)輸出頂點(diǎn)計(jì)數(shù)
   for(j=0;j<G.vexnum;++j) // 初始化ve[]=0 (最小值)
     ve[j]=0;
   while(!StackEmpty(S))
   { // 棧不空
     Pop(S,j);
     Push(T,j); // j號(hào)頂點(diǎn)入T棧并計(jì)數(shù)
     ++count;
     for(p=G.vertices[j].firstarc;p;p=p->nextarc)
     { // 對(duì)j號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1
       k=p->adjvex;
       if(--indegree[k]==0) // 若入度減為0,則入棧
         Push(S,k);
       if(ve[j]+*(p->info)>ve[k])
         ve[k]=ve[j]+*(p->info);
     }
   }
   if(count<G.vexnum)
   {
     printf("此有向網(wǎng)有回路\n");
     return ERROR;
   }
   else
     return OK;
 }

 Status CriticalPath(ALGraph G)
 { // 算法7.14 G為有向網(wǎng),輸出G的各項(xiàng)關(guān)鍵活動(dòng)
   int vl[MAX_VERTEX_NUM];
   SqStack T;
   int i,j,k,ee,el;
   ArcNode *p;
   char dut,tag;
   if(!TopologicalOrder(G,T)) // 產(chǎn)生有向環(huán)
     return ERROR;
   j=ve[0];
   for(i=1;i<G.vexnum;i++) // j=Max(ve[]) 完成點(diǎn)的值
     if(ve[i]>j)
       j=ve[i];
   for(i=0;i<G.vexnum;i++) // 初始化頂點(diǎn)事件的最遲發(fā)生時(shí)間(最大值)
     vl[i]=j; // 完成點(diǎn)的最早發(fā)生時(shí)間
   while(!StackEmpty(T)) // 按拓?fù)淠嫘蚯蟾黜旤c(diǎn)的vl值
     for(Pop(T,j),p=G.vertices[j].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;
     }
   printf(" j  k  dut  ee  el  tag\n");
   for(j=0;j<G.vexnum;++j) // 求ee,el和關(guān)鍵活動(dòng)
     for(p=G.vertices[j].firstarc;p;p=p->nextarc)
     {
       k=p->adjvex;
       dut=*(p->info);
       ee=ve[j];
       el=vl[k]-dut;
       tag=(ee==el)?'*':' ';
       printf("%2d %2d %3d %3d %3d    %c\n",j,k,dut,ee,el,tag); // 輸出關(guān)鍵活動(dòng)
     }
   printf("關(guān)鍵活動(dòng)為:\n");
   for(j=0;j<G.vexnum;++j) // 同上
     for(p=G.vertices[j].firstarc;p;p=p->nextarc)
     {
       k=p->adjvex;
       dut=*(p->info);
       if(ve[j]==vl[k]-dut)
         printf("%s→%s\n",G.vertices[j].data,G.vertices[k].data); // 輸出關(guān)鍵活動(dòng)
     }
   return OK;
 }

 void main()
 {
   ALGraph h;
   printf("請(qǐng)選擇有向網(wǎng)\n");
   CreateGraph(h);
   Display(h);
   CriticalPath(h);
 }