// 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-21.h"
 #include"bo7-2.cpp"
 #include"func7-1.cpp"

 int ve[MAX_VERTEX_NUM]; // 事件最早發(fā)生時(shí)間，全局變量(用于算法7.13和算法7.14)

 typedef int SElemType; // 棧元素類型
 #include"c3-1.h" // 順序棧的存儲(chǔ)結(jié)構(gòu)
 #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ù)湫蛄?   // 頂點(diǎn)棧,S為零入度頂點(diǎn)棧。若G無(wú)回路，則用棧T返回G的一個(gè)拓?fù)湫蛄?且函數(shù)值為OK,否則為ERROR
   int i,k,count=0; // 已入棧頂點(diǎn)數(shù)，初值為0
   int indegree[MAX_VERTEX_NUM]; // 入度數(shù)組，存放各頂點(diǎn)當(dāng)前入度數(shù)
   SqStack S;
   ArcNode *p;
   FindInDegree(G,indegree); // 對(duì)各頂點(diǎn)求入度indegree[]，在func7-1.cpp中
   InitStack(S); // 初始化零入度頂點(diǎn)棧S
   printf("拓?fù)湫蛄校?quot;);
   for(i=0;i<G.vexnum;++i) // 對(duì)所有頂點(diǎn)i
     if(!indegree[i]) // 若其入度為0
       Push(S,i); // 將i入零入度頂點(diǎn)棧S
   InitStack(T); // 初始化拓?fù)湫蛄许旤c(diǎn)棧
   for(i=0;i<G.vexnum;++i) // 初始化ve[]=0(最小值，先假定每個(gè)事件都不受其他事件約束)
     ve[i]=0;
   while(!StackEmpty(S)) // 當(dāng)零入度頂點(diǎn)棧S不空
   {
     Pop(S,i); // 從棧S將已拓?fù)渑判虻捻旤c(diǎn)j彈出
     printf("%s ",G.vertices[i].data);
     Push(T,i); // j號(hào)頂點(diǎn)入逆拓?fù)渑判驐(棧底元素為拓?fù)渑判虻牡?個(gè)元素)
     ++count; // 對(duì)入棧T的頂點(diǎn)計(jì)數(shù)
     for(p=G.vertices[i].firstarc;p;p=p->nextarc)
     { // 對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)
       k=p->data.adjvex; // 其序號(hào)為k
       if(--indegree[k]==0) // k的入度減1，若減為0，則將k入棧S
	 Push(S,k);
       if(ve[i]+*(p->data.info)>ve[k]) // *(p->data.info)是<i,k>的權(quán)值
	 ve[k]=ve[i]+*(p->data.info); // 頂點(diǎn)k事件的最早發(fā)生時(shí)間要受其直接前驅(qū)頂點(diǎn)i事件的
     }                  // 最早發(fā)生時(shí)間和<i,k>的權(quán)值約束。由于i已拓?fù)溆行颍蕍e[i]不再改變
   }
   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]; // 事件最遲發(fā)生時(shí)間
   SqStack T;
   int i,j,k,ee,el,dut;
   ArcNode *p;
   if(!TopologicalOrder(G,T)) // 產(chǎn)生有向環(huán)
     return ERROR;
   j=ve[0]; // j的初值
   for(i=1;i<G.vexnum;i++)
     if(ve[i]>j)
       j=ve[i]; // j=Max(ve[]) 完成點(diǎn)的最早發(fā)生時(shí)間
   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)
     { // 彈出棧T的元素,賦給j,p指向j的后繼事件k,事件k的最遲發(fā)生時(shí)間已確定(因?yàn)槭悄嫱負(fù)渑判?
       k=p->data.adjvex;
       dut=*(p->data.info); // dut=<j,k>的權(quán)值
       if(vl[k]-dut<vl[j])
	 vl[j]=vl[k]-dut; // 事件j的最遲發(fā)生時(shí)間要受其直接后繼事件k的最遲發(fā)生時(shí)間
     }                    // 和<j,k>的權(quán)值約束。由于k已逆拓?fù)溆行颍蕍l[k]不再改變
   printf("\ni ve[i] vl[i]\n");
   for(i=0;i<G.vexnum;i++) // 初始化頂點(diǎn)事件的最遲發(fā)生時(shí)間
   {
     printf("%d   %d     %d",i,ve[i],vl[i]);
     if(ve[i]==vl[i])
       printf(" 關(guān)鍵路徑經(jīng)過(guò)的頂點(diǎn)");
     printf("\n");
   }
   printf("j   k  權(quán)值  ee  el\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->data.adjvex;
       dut=*(p->data.info); // dut=<j,k>的權(quán)值
       ee=ve[j]; // ee=活動(dòng)<j,k>的最早開(kāi)始時(shí)間(在j點(diǎn))
       el=vl[k]-dut; // el=活動(dòng)<j,k>的最遲開(kāi)始時(shí)間(在j點(diǎn))
       printf("%s→%s %3d %3d %3d ",G.vertices[j].data,G.vertices[k].data,dut,ee,el);
       // 輸出各邊的參數(shù)
       if(ee==el) // 是關(guān)鍵活動(dòng)
         printf("關(guān)鍵活動(dòng)");
       printf("\n");
     }
   return OK;
 }

 void main()
 {
   ALGraph h;
   printf("請(qǐng)選擇有向網(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)鍵路徑
 }