- 中文名
- 拓扑排序
- 外文名
- topological-sort
- 别 名
- toposort topsort
- 应用学科
- 计算机科学 图论
一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。
图3-5 这种先后关系的AOV网一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行。如图3-6是一个具有三个顶点的回路，由<A,B>边可得B活动必须在A活动之后，由<B,C>边可得C活动必须在B活动之后，所以推出C活动必然在A活动之后，但由<C,A>边可得C活动必须在A活动之前，从而出现矛盾，使每一项活动都无法进行。这种情况若在程序中出现，则称为死锁或死循环，是必须避免的。
在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological order)，由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。
由AOV网构造出拓扑序列的实际意义是：如果按照拓扑序列中的顶点次序，在开始每一项活动时，能够保证它的所有前驱活动都已完成，从而使整个工程顺序进行，不会出现冲突的情况。 [2]
由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。
(1) 选择一个入度为0的顶点并输出之；
拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。
注意：这里得到的排序并不是唯一的！就好像你早上穿衣服可以先穿上衣也可以先穿裤子，只要里面的衣服在外面的衣服之前穿就行。
拓扑序列 Pascal代码（无优化）
program TopSort;
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);
for i:=1 to m do
begin //读图
readln(a,b);
map[a,b]:=1;
v[b]:=v[b]+1;
end;
i:=0;
link:=map;
while (i<n) do
begin //开始排序
j:=1;
while (v[j]<>0) do inc(j);
v[j]:=-1;
for k:=1 to n do
if link[j,k]=1 then
begin
dec(v[k]);
link[j,k]:=0;
end;
inc(i);
pnt[i]:=j;
end;
for i:=1 to n do
writeln(pnt[i]);
end.
拓扑序列 C++（STL）核心代码
这里的代码可以参考这本书 [3]，这里用了容器，感觉能看明白点。
queue<int>q;
//priority_queue<int,vector<int>,greater<int>>q;
//优先队列的话，会按照数值大小有顺序的输出
//此处为了理解，暂时就用简单队列
int topo()
{
for(inti=1;i<=n;i++)
{
if(indegree[i]==0)
{
q.push(i);
}
}
int temp;
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代码（邻接表+队列优化）
program topsort;
type
node=^link;
link=record
procedure addd(x,y:longint);
var p:node;
begin
new(p);
p^.g:=y;p^.next:=nd[x];
nd[x]:=p;
inc(ru[y]);
end;
begin
readln(n,m);
for a:=1 to m do
begin
readln(x,y);
addd(x,y);
end;
for a:=1 to n do
if ru[a]=0 then begin
inc(stk);
stack[stk]:=a;
end;
be:=0;
repeat
inc(be);
x:=stack[be];
p:=nd[x];
write(x,'');
while p<>nil do
begin
dec(ru[p^.g]);
if ru[p^.g]=0 then begin
inc(stk);
stack[stk]:=p^.g;
end;
p:=p^.next;
end;
until be=stk;
readln;
end.
