預備知識
拓撲排序一個較大的工程往往被劃分成許多子工程，我們把這些子工程稱作活動(activity)。在整個工程中，有些子工程(活動)必須在其它有關子工程完成之後才能開始，也就是說，一個子工程的開始是以它的所有前序子工程的結束為先決條件的，但有些子工程沒有先決條件，可以安排在任何時間開始。為了形象地反映出整個工程中各個子工程(活動)之間的先後關係，可用一個有向圖來表示，圖中的頂點代表活動(子工程)，圖中的有向邊代表活動的先後關係，即有向邊的起點的活動是終點活動的前序活動，只有當起點活動完成之後，其終點活動才能進行。通常，我們把這種頂點表示活動、邊表示活動間先後關係的有向圖稱做頂點活動網(Activity On Vertex network)，簡稱AOV網。
例如，假定一個計算機專業的學生必須完成圖3-4所列出的全部課程。在這裡，課程代表活動，學習一門課程就表示進行一項活動，學習每門課程的先決條件是學完它的全部先修課程。如學習《數據結構》課程就必須安排在學完它的兩門先修課程《離散數學》和《算法語言》之後。學習《高等數學》課程則可以隨時安排，因為它是基礎課程，沒有先修課。若用AOV網來表示這種課程安排的先後關係，則如圖3-5所示。圖中的每個頂點代表一門課程，每條有向邊代表起點對應的課程是終點對應課程的先修課。圖中的每個頂點代表一從圖中可以清楚地看出各課程之間的先修和後續的關係。如課程C5的先修課為C2，後續課程為C4和C6。
一個AOV網應該是一個有向無環圖，即不應該帶有迴路，因為若帶有迴路，則迴路上的所有活動都無法進行。如圖3-6是一個具有三個頂點的迴路，由邊可得B活動必須在A活動之後，由邊可得C活動必須在B活動之後，所以推出C活動必然在A活動之後，但由邊可得C活動必須在A活動之前，從而出現矛盾，使每一項活動都無法進行。這種情況若在程式中出現，則稱為死鎖或死循環，是應該必須避免的。
在AOV網中，若不存在迴路，則所有活動可排列成一個線性序列，使得每個活動的所有前驅活動都排在該活動的前面，我們把此序列叫做拓撲序列(Topological order)，由AOV網構造拓撲序列的過程叫做拓撲排序(Topological sort)。AOV網的拓撲序列不是唯一的，滿足上述定義的任一線性序列都稱作它的拓撲序列。
由AOV網構造出拓撲序列的實際意義是：如果按照拓撲序列中的頂點次序，在開始每一項活動時，能夠保證它的所有前驅活動都已完成，從而使整個工程順序進行，不會出現衝突的情況。
執行步驟
由AOV網構造拓撲序列的拓撲排序算法主要是循環執行以下兩步，直到不存在入度為0的頂點為止。
(1) 選擇一個入度為0的頂點並輸出之；
(2) 從網中刪除此頂點及所有出邊。
循環結束後，若輸出的頂點數小於網中的頂點數，則輸出“有迴路”信息，否則輸出的頂點序列就是一種拓撲序列。
非計算機套用
拓撲排序常用來確定一個依賴關係集中，事物發生的順序。例如，在日常工作中，可能會將項目拆分成A、B、C、D四個子部分來完成，但A依賴於B和D，C依賴於D。為了計算這個項目進行的順序，可對這個關係集進行拓撲排序，得出一個線性的序列，則排在前面的任務就是需要先完成的任務。
注意：這裡得到的排序並不是唯一的！就好像你早上穿衣服可以先穿上衣也可以先穿褲子，只要裡面的衣服在外面的衣服之前穿就行。
計算機語言中
拓撲序列Pascal代碼（無最佳化）programTopSort;
var
map,link:array[1..100,1..100]ofinteger;
v,pnt:array[1..100]ofinteger;
n,m,a,b,i,j,k:integer;
begin
fillchar(map,sizeof(map),0);
fillchar(link,sizeof(link),0);
fillchar(v,sizeof(v),0);
readln(n,m);
fori:=1tomdobegin
readln(a,b);
map[a,b]:=1;
v[b]:=v[b]+1;
end;
i:=0;
link:=map;
while(i<n)dobegin
j:=1;
while(v[j]<>0)doinc(j);
v[j]:=-1;
fork:=1tondoiflink[j,k]=1thenbegin
dec(v[k]);
link[j,k]:=0;
end;
inc(i);
pnt[i]:=j;
end;
fori:=1tondo
ln(pnt[i]);
end.
拓撲序列C++（STL）核心代碼
queue<int>q;
//priority_queue<int,vector<int>,greater<int>>q;
//優先佇列的話，會按照數值大小有順序的輸出
//此處為了理解，暫時就用簡單佇列
inttopo()
{
for(inti=1;i<=n;i++)
{
if(indegree[i]==0)
{
q.push(i);
}
}
inttemp;
while(!q.empty())
{
temp=q.front();//如果是優先佇列，這裡可以是top()
printf("%d->",temp);
q.pop();
for(inti=1;i<=n;i++)//遍歷從temp出發的每一條邊，入度--
{
if(map[temp][i])
{
indegree[i]--;
if(indegree[i]==0)q.push(i);
}
}
}
}
拓撲序列Pascal代碼（鄰接表+佇列最佳化）
programtopsort;
type
node=^link;
link=record
procedureaddd(x,y:longint);
varp:node;
begin
new(p);
p^.g:=y;p^.next:=nd[x];
nd[x]:=p;
inc(ru[y]);
end;
begin
readln(n,m);
fora:=1tomdo
begin
readln(x,y);
addd(x,y);
end;
fora:=1tondo
ifru[a]=0
thenbegin
inc(stk);
stack[stk]:=a;
end;
be:=0;
repeat
inc(be);
x:=stack[be];
p:=nd[x];
write(x,'');
whilep<>nildo
begin
dec(ru[p^.g]);
ifru[p^.g]=0
thenbegin
inc(stk);
stack[stk]:=p^.g;
end;
p:=p^.next;
end;
untilbe=stk;
readln;
end.
這裡主要是將入度為零的點加入佇列stack，直接在佇列內擴展即可，效率為O(n+m)
拓撲學
拓撲學是近代發展起來的一個研究連續性現象的數學分支。中文名稱起源於希臘語Τοπολογία的音譯。Topology原意為地貌，於19世紀中期由科學家引入，當時主要研究的是出於數學分析的需要而產生的一些幾何問題。發展至今，拓撲學主要研究拓撲空間在拓撲變換下的不變性質和不變數。
