學生選修課程問題
頂點——表示課程
有向弧——表示先決條件，若課程i是課程j的先決條件，則圖中有弧（i,j）
學生應按怎樣的順序學習這些課程，才能無矛盾、順利地完成學業——拓撲排序
拓撲序列是有向無環圖中各頂點構成的有序序列。該序列滿足如下條件：如果圖中一頂點vi到另一頂點vj存在一條路徑，那麼vj在此圖的拓撲排序序列中位於vi之後。
有向無環圖”（Directed Acyclic Graph，簡稱DAG
AOV網 (Activity On Vertex network): 一個“可行的” AOV 網絡必須是DAG。否則圖中有回路，從而就不能確定回路中的活動究竟哪個先實施。
頂點表示活動，
弧表示活動間的優先關系，
注意：
AOV網中的弧表示活動之間存在某種制約關系：若
void ToplogicalSort ( Graph G, int TopNum[ ] )
{
int Counter; /* 拓撲序號，用以標識每個頂點輸出的次序*/
int v, w;
int *InDegree = (int *)malloc( G.n * sizeof(int) );
GetInDegree(G, InDegree); /* 計算圖G中各頂點的入度 */
for( Counter = 0; Counter < G.n; Counter++ ) {
v = FindNewVertexOfDegreeZero( );
/* 查找入度為0的頂點，若找到，則返回頂點在頂點數組的下標。若找不到入度為0的頂點，返回-1 */
if ( v == -1 ) {
printf( “圖存在環路”);
break;
}
TopNum[v] = Counter;
for( G中關於v 的每個鄰接點w )
Indegree[w]--; /* 與頂點v相連的各頂點的入度減1 */
}
}
void ToplogicalSort ( GraphAdjList GL, int * TopNum )
{
Queue queue; EdgeNode *p; int Counter = 0; int v, w;
//int *InDegree = (int *)malloc( G.n * sizeof(int) );
// GetInDegree(G, InDegree); /* 計算圖G中各頂點的入度 */
queue = InitQueue( GL->numVertexes ); /* 創建空隊列 */
for( v = 0; v <GL->numVertexes; v++ )
if( GL->adjList[v].in==0 ) EnQueue( &queue, v );
while( ! QueueEmpty(queue) ) {
v = DeQueue( &queue);
TopNum[v] = ++Counter; /* 賦頂點拓撲排序序號 */
for( p=GL->adjList[v].firstedge;p!=NULL;p=p->next)
if( --GL->adjList[p->adjvex].in == 0 )
EnQueue( &queue, p->adjvex );
}
if( Counter != GL->numVertexes )
printf( "圖存在環路\n" );
DisposeQueue(&queue); /* 釋放隊列空間*/
//free(InDegree);
}
與AOV網相對應的是AOE(Activity On Edge) ，是邊表示活動的有向無環圖。
頂點表示事件(Event)，每個事件表示在它之前的活動已完成，在它之後的活動可以開始；
弧表示活動，弧上的權值表示相應活動所需的時間或費用拓撲排序主要是為解決一個工程能否順利進行的問題。
關鍵路徑是解決工程完成需要的最短時間問題。
AOV網與AOE網的區別：
AOV網，頂點表示活動，邊描述活動之間的制約關系
AOE網，邊上的權值表示活動持續的時間，
建立在活動之間制約關系沒有矛盾的基礎上，
討論完成整個工程至少需要多少時間；或者為縮短完成工程所需時間，應當加快哪些活動等問題。
路徑長度—路徑上各活動持續時間之和
關鍵路徑—從源點到匯點具有最大路徑長度的路徑
關鍵活動—關鍵路徑上的活動。關鍵活動是影響整個工程的關鍵，延遲就會影響整個工期的活動。
最早發生時間—設v0是起點，從v0到vi的最長路徑長度稱為事件vi的最早發生時間，即是以vi為尾的所有活動的最早發生時間。
⑴ 算法思想
① 利用拓撲排序求出AOE網的一個拓撲序列；
② 從拓撲排序的序列的第一個頂點(源點)開始，按拓撲順序依次計算每個事件的最早發生時間ve(i) ；
從拓撲排序的序列的最後一個頂點(匯點)開始，按逆拓撲順序依次計算每個事件的最晚發生時間vl(i) ；
求出各活動的最早發生時間e(i)和最晚發生時間l(e),同時求出ai的時間余量，時間余量=0的那些活動就是關鍵活動。
用帶權的有向圖表示一個交通運輸網，圖中：
頂點：城市
邊：城市間的交通聯系
權：此線路的長度或沿此線路運輸所花的時間或費用等
問題：
兩地之間是否有通路?
在有多條通路的情況下，哪條最短?
將一條路徑的起始頂點稱為源點，最後一個頂點稱為終點。
對於給定的有向圖G=(V，E)及單個源點V0，求V0到G的其余各頂點的最短路徑。 針對單源點的最短路徑問題，Dijkstra提出了一種按路徑長度遞增次序產生最短路徑的算法，即迪傑斯特拉(Dijkstra)算法。
初使時令 S={V0},T={其余頂點}，T中頂點對應的距離值
若存在 V0,Vi，為V0,Vi弧上的權值
若不存在 V0, Vi，為?
從T中選取一個其距離值為最小的頂點W，加入S
對T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值
重復上述步驟，直到S中包含所有頂點，即S=V為止
算法實現
圖用帶權鄰接矩陣存儲
數組dist[ ]存放當前找到的從源點V0到每個終點的最短路徑長度（這些路徑中間只經過集合S中的頂點），其初態為圖中直接路徑權值
數組pre[ ]表示從V0到各終點的最短路徑上，此頂點的前一頂點的序號；若從V0到某終點無路徑，則用0作為其前一頂點的序號
