拓撲排序演算法是
拓撲排序常見的有兩種演算法，一種是反復找入度為0的點，一種是利用DFS時的時間戳來求拓撲序
下面的程序時後一種演算法，圖用臨界表存儲，在遍歷的同時，完成了拓撲排序
#include<cstdio>
#include<cstring>
struct edgetype
{
int to;
edgetype *next;
} edge[1000000];
edgetype *link[10000];
int n , m, DFStime;
int reach[10000], order[10000];
bool DFS(int now)
{
if (reach[now] == 2) return true;
if (reach[now] == 1) return false;
reach[now] = 1;
for (edgetype *e = link[now]; e; e = e -> next)
if (!DFS(e -> to)) return false;
reach[now] = 2;
order[DFStime++] = now;
return true;
}
int main()
{
scanf("%d%d" ,&n, &m);
for (int i = 0; i < m; ++i)
{
int a,b;
scanf("%d%d",&a,&b);
edge[i].to = b;
edge[i].next = link[a];
link[a] = edge + i;
}
memset(reach , -1, sizeof(reach));
DFStime = 0;
for (int i = 0; i < n; ++i)
if (reach[i] == -1)
if (!DFS(i))
{
puts("There is a cycle in the graph!");
return 0;
}
for (int i = n - 1; i >= 0; --i)
printf("%d ", order[i]);
}
2. 求拓撲排序演算法的詳細講解
3.1AOV網
在現代化管理中，人們常用有向圖來描述和分析一項工程的計劃和實施過程，一個工程常被分為多個小的子工程，這些子工程被稱為活動（Activity)，在有向圖中若以頂點表示活動，有向邊表示活動之間的先後關系，這樣的圖簡稱為AOV網。如下圖是計算機專業課程之間的先後關系：
基礎知識課程應先於其它所有課程，pascal語言課程應先於數據結構。
3. 2 拓撲排序
在AOV網中為了更好地完成工程，必須滿足活動之間先後關系，需要將各活動排一個先後次序即為拓撲排序。如上圖的拓撲排序
基礎知識；Pascal；數據結構；離散數學。或
基礎知識；離散數學Pascal；數據結構。
拓撲排序的方法和步驟：
（1）在圖中選一個沒有前趨的頂點並輸出之
（2）刪除該頂點及由它發出的各邊，直到圖中不存在沒有前趨的頂點為止。
若圖中存在迴路，拓撲排序無法進行。
以下是將一AOV網進行拓撲排序的演算法：
網採用鄰接矩陣A表示,若a[i，j]=1，表示活動i先於j，a[i，j]=0，表示活動i與j不存在先後關系。
（1）計算各頂點的入度
（2）找入度為零的點輸出之，刪除該點，且與該點關聯各點的入度減1
（3）若所有頂點都輸出完畢。
程序如下：
program tppv;
const maxn=100;
var
map:array[1..maxn,1..maxn] of byte;
into:array[1..maxn] of byte;
n,i,j,k:byte;
procere init;
var
i,j:integer;
begin
read(n);
for i:=1 to n do
for j:=1 to n do
begin
read(map[i,j]);
inc(into[j]);
end;
end;
begin
init;
for i:=1 to n do
begin
j:=1;
while (j<=n)and(into[j]<>0) do inc(j);
write(j,' ');
into[j]:=255;
for k:=1 to n do
if map[j,k]=1 then dec(into[k]);
end;
end.
3.3應用舉例與練習
例：士兵排隊問題：
有N個士兵（1<=N<=100),編號依次為1,2,...,N.隊列訓練時，指揮官要把士兵從高到矮排成一行，但指揮官只知道「1 比2 高，7 比 5高」這樣的比較結果。
輸入文件：第一行為數N（N〈=100）；表示士兵的個數。以下若干行每行兩個數A，B 表示A高於B。
輸出文件：給出一個合法的排隊序列。
程序如下：
program tppv;
const maxn=100;
var
map:array[1..maxn,1..maxn] of byte;
into:array[1..maxn] of byte;
n,i,j,k:byte;
fp:text;
procere init;
var
i,j:integer;
begin
assign(fp,'tp.txt');
reset(fp);
readln(fp,n);
fillchar(map,sizeof(map),0);
fillchar(into,sizeof(into),0);
while not(seekeof(fp)) do
begin
readln(fp,i,j);
map[i,j]=1 ;
inc(into[j]);
end;
close(fp);
end;
begin
init;
for i:=1 to n do
begin
j:=1;
while (j<=n)and(into[j]<>0) do inc(j);
write(j,' ');
into[j]:=255;
for k:=1 to n do
if map[j,k]=1 then dec(into[k]);
end;
end.
練習：
Z語言問題：Z語言的基本字母也是26個，不妨用a到z表示，但先後順序與英語不同。
現在按Z語言的順序給出了N個單詞，請依照這些單詞給出一個可能的Z語言字母順序。
輸入文件：第一行一個數N（N<=100)表示單詞的個數。
第二行到第N+1行，每行一個單詞。
輸出文件：僅一行，可能的字母順序。
(圖不好粘貼）