预备知识

一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。

例如，假定一个计算机专业的学生必须完成图3-4所列出的全部课程。在这里，课程代表活动，学习一门课程就表示进行一项活动，学习每门课程的先决条件是学完它的全部先修课程。如学习《数据结构》课程就必须安排在学完它的两门先修课程《离散数学》和《算法语言》之后。学习《高等数学》课程则可以随时安排，因为它是基础课程，没有先修课。若用AOV网来表示这种课程安排的先后关系，则如图3-5所示。图中的每个顶点代表一门课程，每条有向边代表起点对应的课程是终点对应课程的先修课。从图中可以清楚地看出各课程之间的先修和后续的关系。如课程C5的先修课为C2，后续课程为C4和C6。

一个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网构造出拓扑序列的实际意义是：如果按照拓扑序列中的顶点次序，在开始每一项活动时，能够保证它的所有前驱活动都已完成，从而使整个工程顺序进行，不会出现冲突的情况。

执行步骤

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。

(1) 选择一个入度为0的顶点并输出之；

(2) 从网中删除此顶点及所有出边。

循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

非计算机应用

拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。

注意：这里得到的排序并不是唯一的！就好像你早上穿衣服可以先穿上衣也可以先穿裤子，只要里面的衣服在外面的衣服之前穿就行。

应用

拓扑序列 Pascal代码（无优化）

1. program TopSort;
2. var
3.     map,link:array[1..100,1..100]ofinteger;
4.     v,pnt:array[1..100]ofinteger;
5.     n,m,a,b,i,j,k:integer;
6. begin
7.     fillchar(map,sizeof(map),0);
8.     fillchar(link,sizeof(link),0);
9.     fillchar(v,sizeof(v),0);                          //初始化
10.     readln(n,m);
11.     for i:=1 to m do
12.         begin                                       //读图
13.             readln(a,b);
14.             map[a,b]:=1;
15.             v[b]:=v[b]+1;
16.         end;
17.     i:=0;
18.     link:=map;
19.     while (i<n) do
20.         begin                               //开始排序                  
21.             j:=1;
22.             while (v[j]<>0) do inc(j);
23.             v[j]:=-1;
24.             for k:=1 to n do
25.                 if link[j,k]=1 then
26.                     begin
27.                         dec(v[k]);
28.                         link[j,k]:=0;
29.                     end;
30.             inc(i);
31.             pnt[i]:=j;
32.         end;
33.     for i:=1 to n do
34.         writeln(pnt[i]);
35. end.

拓扑序列 C++（STL）核心代码

这里的代码可以参考这本书 [3]  ，这里用了容器，感觉能看明白点。

1. queue<int>q;
2. //priority_queue<int,vector<int>,greater<int>>q;
3. //优先队列的话，会按照数值大小有顺序的输出
4. //此处为了理解，暂时就用简单队列
5. int topo()
6. {
7.     for(inti=1;i<=n;i++)
8.     {
9.         if(indegree[i]==0)
10.         {
11.             q.push(i);
12.         }
13.     }
14.  
15.     int temp;
16.     while(!q.empty())
17.     {
18.         temp=q.front();//如果是优先队列，这里可以是top()
19.         printf("%d->",temp);
20.         q.pop();
21.         for(inti=1;i<=n;i++)//遍历从temp出发的每一条边，入度--
22.         {
23.             if(map[temp][i])
24.             {
25.                 indegree[i]--;
26.                 if(indegree[i]==0)q.push(i);
27.             }
28.         }
29.     }
30. }

拓扑序列 Pascal代码（邻接表+队列优化）

1. program topsort;
2. type
3. node=^link;
4. link=record
5.  
6. procedure addd(x,y:longint);
7. var p:node;
8. begin
9. new(p);
10. p^.g:=y;p^.next:=nd[x];
11. nd[x]:=p;
12. inc(ru[y]);
13. end;
14. begin
15. readln(n,m);
16. for a:=1 to m do
17. begin
18. readln(x,y);
19. addd(x,y);
20. end;
21. for a:=1 to n do
22. if ru[a]=0 then begin
23. inc(stk);
24. stack[stk]:=a;
25. end;
26. be:=0;
27. repeat
28. inc(be);
29. x:=stack[be];
30. p:=nd[x];
31. write(x,'');
32. while p<>nil do
33. begin
34. dec(ru[p^.g]);
35. if ru[p^.g]=0 then begin
36. inc(stk);
37. stack[stk]:=p^.g;
38. end;
39. p:=p^.next;
40. end;
41. until be=stk;
42. readln;
43. end.

这里主要是将入度为零的点加入队列stack，直接在队列内扩展即可，效率为O(n+m)

拓扑学

拓扑学是近代发展起来的一个研究连续性现象的数学分支。中文名称起源于希腊语Τοπολογία的音译。Topology原意为地貌，于19世纪中期由科学家引入，当时主要研究的是出于数学分析的需要而产生的一些几何问题。发展至今，拓扑学主要研究拓扑空间在拓扑变换下的不变性质和不变量。