拓撲排序

拓撲序:如果圖中從V到W有一條有向路徑,則V一定排在W之前。滿足此條件的頂點序列稱為一個拓撲序。獲得一個拓撲序的過程就是拓撲排序。AOV如果有合理的拓撲序,則必定是有向無環圖(Directed Acyclic Graph,DAG)

每次輸出沒有前驅頂點的課程。即輸出入度為0的頂點。

void TopSort()
{   for(cnt=0;cnt<|V|;cnt  )
{ V=未輸出的入度為0的頂點;
if(這樣的點不存在)
{cout<<"圖中有迴路”;
break;
}
輸出v,或者記錄V的輸出編號;
for(V的每個鄰接點w)
Indegree[w]--;
}
}

隨時將入度為0的頂點放入一個容器中

void TopSort()
{  for(圖中每個頂點)
if(Indegree[V]==0)
Enqueue(V,Q);
while(!IsEmpty(Q))
{   V=Dequeue(Q);
輸出V,cnt  ;
for(V的每個鄰接點w)
if(--Indegree[W]==0)
Enqueue(W,Q);
}
if(cnt!=|V|)
cout<<"圖中有迴路";
}

關鍵路徑問題

AOE(Activity On Edge)網路

一般用於安排專案的工序

D<I,J>=Latest[j]-Earliest[i]-C<i,j>//機動時間

關鍵路徑:由絕對不允許延誤的活動組成的路徑,如將關鍵路徑加快進度,則整個專案就能提前完工。