拓扑排序算法是
拓扑排序常见的有两种算法，一种是反复找入度为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行，每行一个单词。
输出文件：仅一行，可能的字母顺序。
(图不好粘贴）