拓撲排序和關鍵路徑是基於無環的有向圖。
主要用來表示工程進度中各個事件之間的關系。
拓撲排序和關鍵路徑 使用鄰接表存儲數據，最小生成樹和最短路徑用 鄰接矩陣 存儲數據。
1、拓撲排序
AOV網：在一個表示工程的有向圖中，用固定點表示活動，用弧表示活動之間的優先級關系，這樣的有向圖為頂點表示活動的網，我們稱之為AOV網Activity On Vertex Network）
拓撲排序：是將一個AOV網的各個頂點按一定順序排列，要求滿足若存在<Vi，Vj>，則排序中的頂點Vi必在頂點Vj之前。對於同一幅圖，拓撲排序可有多個拓撲排序。
在顯示生活中，用到的拓撲排序的例子：
學校課程布置圖，要先修完一些基礎課，才可以繼續修專業課，以計算機軟件專業為例，在《程序設計基礎》和《離散數學》課程學完之前就不能開始學習《數據結構》，這些先決條件定義了課程之間的優先領先）關系。
算法：
1）從有向圖中選擇一個無前驅入度為0）的頂點輸出。
2）刪除此頂點，並刪除已此頂點為為尾的弧。
3）重復1），2）步驟，知道輸出全部頂點或者AOV網中不存在入度為0的頂點。
具體實現代碼：
用棧來保存入度為0的頂點，和更新後入度為0的頂點
#include <stdio.h>
#define MAXVEX 100
typedef struct EdgeNode /*邊表節點*/
{
int adjvex; /*鄰接點域，存儲該頂點對應的下表*/
int weight; /*用於存儲權值，對於非網圖可以不需要*/
struct EdgeNode *next; /*鏈域，指向下一個鄰節點*/
}EdgeNode;
typedef struct VertexNode /*頂點表節點*/
{
int in; /*頂點入度*/
int data; /*頂點域，存儲頂點信心*/
EdgeNode *firstedge; /*邊表頭指針*/
}VertexNode, Adjlist[MAXVEX];
typedef struct
{
Adjlist adjList;
int numVertexes;
int numEdges; /*圖中當前頂點數和邊數*/
}graphAdjList, *GraphAdjList;
/*拓撲排序，若GL無回路，則輸出拓撲排序序列並返回OK，若有回路返回ERROR*/
int TopoLogicalSort(GraphAdjList GL)
{
EdgeNode *e;
int i,k,gettop;
int top = 0; /*用於棧指針下表*/
int count = 0; /*用於統計輸出頂點的個數*/
int *stack; /*建棧用於存儲入度為0的頂點*/
stack = (int*)malloc(GL->numVertexes *sizeof(int)); //動態分配內存，大小為n個頂點(最多有n個頂點入度為0，因為圖總共有n個頂點)
for(i = 0; i<GL->numVertexes; i++)
if(GL->adjList[i].in == 0) /*將入度為0的頂點入棧*/
stack[++top] = i;
while(top != 0)
{
gettop = stack[top--]; /*出棧*/
printf("%d -> ",GL->adjList[gettop].data); /*打印此頂點*/
count++; /*統計輸出頂點數*/
for(e=GL->adjList[gettop].firstedge; e！; e=e->next)
{ /*對此頂點弧表遍歷*/
k = e->adjvex;
if(--GL->adjList[k].in == 0) //將k號頂點鄰接點的入度減1,且減1後，入度為0的頂點需要存到棧中
stack[++top] = k;
}
}
if(count < GL->numVertexes) /*如果count小於頂點數，說明存在環*/
return -1;
else
return 0;
}
分析整個算法，對一個具有n個頂點e條弧的AOV網來說，將入度為0的頂點入棧的時間復雜度為O(n)，而之後的while循環中，每個頂點入一次棧，出一次棧，入度減1的操作執行了e次，所以整個算法時間復雜度為O(n+e)。
2、關鍵路徑
拓撲排序是解決一個工程能否順序進行的問題，但有時還需解決工程完成需要的最短時間。
AOE網：在一個表示工程帶權的有向圖中，用頂點表示事件，用有向邊表示活動，用邊上的權值表示活動的持續時間，這種用有向圖的邊表示活動的網，我們稱之為AOE網Activity On Edge Network）
用ve(i)表示事件即頂點)i的最早開始時間，用vl(i)表示事件i的最開始時間，如果活動k由弧<m,n>表示，用dut(<m,n>)表示活動的持續時間，則有：
e(k) = ve(m)
l(k) = vl(n) - dut(<m,n>)
求解關鍵路徑的具體算法假設圖中有n個頂點)
(1) 從開始頂點V0出發，假設ve(0)=0，然後按照拓撲有序求出其他各頂點i的最早開始時間ve(i)，如果得到拓撲序列中頂點數目小於圖中的頂點數，則表示圖中存在回路，算法結束，否則繼續執行。
2）從結束頂點Vn出發，假設vl(n-1) = ve(n-1);然後求出各頂點i的最晚發生時間。
3）根據頂點的最早發生時間，和最晚發生時間，依次求出出每條弧的最早開始時間和最晚開始時間，如果兩只相等，則為關鍵活動。關鍵活動組成的路徑則為關鍵路徑。
具體實現代碼：
#include <stdio.h>
#define MAXVEX 100
/*首先聲明幾個全局變量*/
int *etv,*ltv; /*時間的最早發生時間和最遲發生時間*/
int *stack2; /*用於存儲拓撲序列的棧*/
int top2; /*用於stack2的指針*/
typedef struct EdgeNode /*邊表節點*/
{
int adjvex; /*鄰接點域，存儲該頂點對應的下表*/
int weight; /*用於存儲權值，對於非網圖可以不需要*/
struct EdgeNode *next; /*鏈域，指向下一個鄰節點*/
}EdgeNode;
typedef struct VertexNode /*頂點表節點*/
{
int in; /*頂點入度*/
int data; /*頂點域，存儲頂點信心*/
EdgeNode *firstedge; /*邊表頭指針*/
}VertexNode, Adjlist[MAXVEX];
typedef struct
{
Adjlist adjList;
int numVertexes;
int numEdges; /*圖中當前頂點數和邊數*/
}graphAdjList, *GraphAdjList;
/*拓撲排序，若GL無回路，則輸出拓撲排序序列並返回OK，若有回路返回ERROR*/
int TopoLogicalSort(GraphAdjList GL)
{
EdgeNode *e;
int i,k,gettop;
int top = 0; /*用於棧指針下表*/
int count = 0; /*用於統計輸出頂點的個數*/
int *stack; /*建棧用於存儲入度為0的頂點*/
stack = (int*)malloc(GL->numVertexes *sizeof(int)); //動態分配內存，大小為n個頂點(最多有n個頂點入度為0，因為圖總共有n個頂點)
for(i = 0; i<GL->numVertexes; i++)
if(GL->adjList[i].in == 0) /*將入度為0的頂點入棧*/
stack[++top] = i;
top2 = 0;
etv = (int*) malloc(GL->numVertexes*sizeof(int)); /*事件的最早發生時間*/
for(i=0;i<GL->numVertexes; i++)
etv[i] = 0;
stack2 = (int*) malloc(GL->numVertexes*sizeof(int)); /*初始化*/
while(top != 0)
{
gettop = stack[top--]; /*出棧*/
printf("%d -> ",GL->adjList[gettop].data); /*打印此頂點*/
stack2[++top2] = gettop; /*將彈出的頂點序列號壓入拓撲序列的棧中*/
count++; /*統計輸出頂點數*/
for(e=GL->adjList[gettop].firstedge; e; e=e->next)
{ /*對此頂點弧表遍歷*/
k = e->adjvex;
if(--GL->adjList[k].in == 0) //將k號頂點鄰接點的入度減1,且減1後，入度為0的頂點需要存到棧中
stack[++top] = k;
if((etv[gettop]+e->weight)>etv[k]) /*求各頂點時間最早發生時間*/
etv[k] = etv[gettop] + e->weight; /*某個頂點的最早發生時間= 和他相關的活動必須全部完成*/
}
}
if(count < GL->numVertexes) /*如果count小於頂點數，說明存在環*/
return -1;
else
return 0;
}
/*求關鍵路徑，GL為有向網，輸出GL的各項關鍵活動*/
void CriticalPath(GraphAdjList GL)
{
EdgeNode *e;
int i,gettop,k,j;
int ete,lte; /*聲明活動最早發生時間和最遲發生時間*/
TopoLogicalSort(GL); /*求拓撲序列，計算數組etv和stack2的值*/
ltv = (int*) malloc(GL->numVertexes*sizeof(int)); /*時間的最晚發生時間*/
for(i= 0; i<GL->numVertexes;i++)
ltv[i]=etv[GL->numVertexes-1]; /*初始化ltv[i] 為工程完成的最早時間，etv[i]初始化為0*/
while(top2!=0) /*計算ltv*/
{
gettop = stack2[top2--];
for(e=GL->adjList[gettop].firstedge;e!=NUll;e=e->next)
{/*求各定點事件的最遲發生時間ltv值*/
k=e->adjvex;
if(ltv[k]-e->weight<ltv[gettop])
ltv[gettop]= ltv[k]-e->weight; /*求最晚發生時間，是從拓撲序列的最後一個頂點逆著推導*/
}
}
for(j=0;j<GL->numVertexes;j++) /*求關鍵活動*/
{
for(e=GL->adjList[j].firstedge;e!=NULL;e=e->next)
{
k=e->adjvex;
ete = etv[j]; /*活動最早開始時間*/
lte = ltv[k] - e->weight;/*活動最晚發生時間*/
if(ete ==lte)
printf("<v%d,v%d> length: %d, ",GL->adjList[j].data,GL->adjList[k].data,e->weight);
}
}
}
本文出自 “李海川” 博客，請務必保留此出處http://lihaichuan.blog.51cto.com/498079/1293633
