// algo7-8.cpp 求關(guān)鍵路徑。實現(xiàn)算法7.13、7.14的程序
 #include"c1.h"
 #include"func7-6.cpp" // 包括頂點信息類型的定義及對它的操作
 #include"func7-7.cpp" // 弧的相關(guān)信息類型的定義及對它的操作
 #include"c7-2'.h" // 圖的鄰接表存儲結(jié)構(gòu)(與單鏈表的變量類型建立聯(lián)系)
 #include"bo7-2.cpp" // 圖的鄰接表存儲結(jié)構(gòu)的基本操作
 #include"func7-5.cpp" // 求頂點入度的函數(shù)
 typedef int SElemType; // 定義棧元素類型為整型(存儲頂點序號)
 #include"c3-1.h" // 順序棧的存儲結(jié)構(gòu)
 #include"bo3-1.cpp" // 順序棧的基本操作
 Status TopologicalOrder(ALGraph &G,SqStack &T)
 { // 有向網(wǎng)G采用鄰接表存儲結(jié)構(gòu)，求各頂點事件的最早發(fā)生時間ve(存儲在G中)。修改算法7.13
   // T為拓撲序列頂點棧，S為零入度頂點棧。若G無回路，則用棧T返回G的一個拓撲序列，
   // 且函數(shù)值為OK；否則為ERROR
   int i,k,count=0; // 已入棧頂點數(shù)，初值為0
   int indegree[MAX_VERTEX_NUM]; // 入度數(shù)組，存放各頂點當(dāng)前入度數(shù)
   SqStack S;
   ArcNode *p;
   FindInDegree(G,indegree); // 對各頂點求入度indegree[]，在func7-5.cpp中
   InitStack(S); // 初始化零入度頂點棧S
   printf("拓撲序列：");
   for(i=0;i<G.vexnum;++i) // 對所有頂點i
     if(!indegree[i]) // 若其入度為0
       Push(S,i); // 將i入零入度頂點棧S
   InitStack(T); // 初始化拓撲序列頂點棧
   for(i=0;i<G.vexnum;++i) // 初始化ve=0(最小值，先假定每個事件都不受其他事件約束)
     G.vertices[i].data.ve=0;
   while(!StackEmpty(S)) // 當(dāng)零入度頂點棧S不空
   { Pop(S,i); // 從棧S將已拓撲排序的頂點彈出，并賦給i
     Visit(G.vertices[i].data); // 輸出該頂點的名稱
     Push(T,i); // j號頂點入逆拓撲排序棧T(棧底元素為拓撲排序的第1個元素)
     ++count; // 對入棧T的頂點計數(shù)
     for(p=G.vertices[i].firstarc;p;p=p->nextarc)
     { // 對i號頂點的每個鄰接頂點
       k=p->data.adjvex; // 其序號為k
       if(--indegree[k]==0) // k的入度減1，若減為0，則將k入棧S
         Push(S,k);
       if(G.vertices[i].data.ve+p->data.info->weight>G.vertices[k].data.ve)
       // 頂點i事件的最早發(fā)生時間+<i,k>的權(quán)值>頂點k事件的最早發(fā)生時間
         G.vertices[k].data.ve=G.vertices[i].data.ve+p->data.info->weight;
         // 頂點k事件的最早發(fā)生時間=頂點i事件的最早發(fā)生時間+<i,k>的權(quán)值
     }   // 由于i已拓撲有序，故G.vertices[i].data.ve不再改變
   }
   if(count<G.vexnum)
   { printf("此有向網(wǎng)有回路\n");
     return ERROR;
   }
   else
     return OK;
 }

 Status CriticalPath(ALGraph &G)
 { // G為有向網(wǎng)，輸出G的各項關(guān)鍵活動。修改算法7.14
   SqStack T;
   int i,j,k;
   ArcNode *p;
   if(!TopologicalOrder(G,T)) // 產(chǎn)生有向環(huán)
     return ERROR;
   j=G.vertices[0].data.ve; // j的初值
   for(i=1;i<G.vexnum;i++) // 在所有頂點中，找ve的最大值
     if(G.vertices[i].data.ve>j)
       j=G.vertices[i].data.ve; // j=Max(ve) 完成點的最早發(fā)生時間
   for(i=0;i<G.vexnum;i++) // 初始化頂點事件的最遲發(fā)生時間
     G.vertices[i].data.vl=j; // 為完成點的最早發(fā)生時間(最大值)
   while(!StackEmpty(T)) // 按拓撲逆序求各頂點的vl值
     for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc)
     { // 彈出棧T的元素，賦給j，p指向頂點j的后繼事件(出弧)頂點k，
       // 事件k的最遲發(fā)生時間已確定(因為是逆拓撲排序)
       k=p->data.adjvex; // 后繼事件頂點的序號
       if(G.vertices[k].data.vl-p->data.info->weight<G.vertices[j].data.vl)
       // 事件j的最遲發(fā)生時間>其直接后繼事件k的最遲發(fā)生時間-<j,k>的權(quán)值
         G.vertices[j].data.vl=G.vertices[k].data.vl-p->data.info->weight;
         // 事件j的最遲發(fā)生時間=事件k的最遲發(fā)生時間-<j,k>的權(quán)值
     }   // 由于k已逆拓撲有序，故G.vertices[k].data.vl不再改變
   printf("\ni  ve  vl\n");
   for(i=0;i<G.vexnum;i++) // 對于每個頂點
   { printf("%d ",i); // 輸出序號
     Visitel(G.vertices[i].data); // 輸出ve、vl值，在func7-6.cpp中
     if(G.vertices[i].data.ve==G.vertices[i].data.vl)
     // 事件(頂點)的最早發(fā)生時間=最遲發(fā)生時間
       printf(" 關(guān)鍵路徑經(jīng)過的頂點");
     printf("\n");
   }
   printf("j   k  權(quán)值  ee  el\n"); // 以下求ee，el和關(guān)鍵活動
   for(j=0;j<G.vexnum;++j) // 對于每個頂點j
     for(p=G.vertices[j].firstarc;p;p=p->nextarc)
     { // p依次指向其鄰接頂點(直接后繼事件)
       k=p->data.adjvex; // 鄰接頂點(直接后繼事件)序號
       p->data.info->ee=G.vertices[j].data.ve;
       // ee(活動<j,k>的最早開始時間)=(頂點j)事件最早發(fā)生時間
       p->data.info->el=G.vertices[k].data.vl-p->data.info->weight;
       // el(活動<j,k>的最遲開始時間)=(頂點k)事件最遲發(fā)生時間-<j,k>的權(quán)值
       printf("%s→%s",G.vertices[j].data.name,G.vertices[k].data.name); // 輸出弧
       OutputArcwel(p->data.info); // 輸出弧的權(quán)值、ee和el，在func7-7.cpp中
       if(p->data.info->ee==p->data.info->el)
       // 活動(弧)的最早開始時間=活動的最遲開始時間
         printf("關(guān)鍵活動");
       printf("\n");
     }
   return OK;
 }

 void main()
 {
   ALGraph h;
   printf("請選擇有向網(wǎng)\n");
   CreateGraph(h); // 構(gòu)造有向網(wǎng)h，在bo7-2.cpp中
   Display(h); // 輸出有向網(wǎng)h，在bo7-2.cpp中
   CriticalPath(h); // 求h的關(guān)鍵路徑
 }