什么是拓扑排序
拓扑排序，简单地说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
偏序形式定义： 设R是集合A上的一个二元关系，若R满足： Ⅰ 自反性：对任意x∈A，有xRx； Ⅱ 反对称性（即反对称关系）：对任意x,y∈A，若xRy，且yRx，则x=y； Ⅲ 传递性：对任意x, y,z∈A，若xRy，且yRz，则xRz。[1] 则称R为A上的偏序关系，通常记作≼。注意这里的≼不必是指一般意义上的“小于或等于”。 若然有x≼y，我们也说x排在y前面（x precedes y）。——摘自百度百科 全序形式定义： 设集合X上有一全序关系，如果我们把这种关系用 ≤ 表述，则下列陈述对于 X 中的所有 a, b 和 c 成立： 如果 a ≤ b 且 b ≤ a 则 a = b (反对称性) 如果 a ≤ b 且 b ≤ c 则 a ≤ c (传递性) a ≤ b 或 b ≤ a (完全性) 配对了在其上相关的全序的集合叫做全序集合（totally ordered set）、线序集合（linearly ordered set）、简单序集合（simply ordered set）或链（chain）。链还常用来描述某个偏序的全序子集，比如在佐恩引理中。 关系的完全性可以如下这样描述：对于集合中的任何一对元素，在这个关系下都是相互可比较的。 注意完全性条件蕴涵了自反性，也就是说，a ≤ a。因此全序也是偏序（自反的、反对称的和传递的二元关系）。全序也可以定义为“全部”的偏序，就是满足“完全性”条件的偏序。 可作为选择的，可以定义全序集合为特殊种类的格，它对于集合中的所有 a, b 有如下性质： 我们规定 a ≤ b 当且仅当。可以证明全序集合是分配格。 全序集合形成了偏序集合的范畴的全子范畴，通过是关于这些次序的映射的态射，比如，映射 f 使得"如果 a ≤ b 则 f(a) ≤ f(b)"。 在两个全序集合间的关于两个次序的双射是在这个范畴内的同构。——摘自百度百科
一个表示偏序的有向图可用来拜师一个流程图。它或者是一个施工流程图，或者是一个产品生产的流程图，再或是一个数据流图（每个顶点表示一个过程）。图中每一条有向边表示两个子工程之间的次序关系（领先关系）。
怎么获得拓扑排序
- 在有向图中选一个没有前驱的顶点且输出之
- 从图中删除该顶点和所有以它为尾的弧
- 重复上述两步直到所有顶点均已输出或当前图中不存在无前驱的顶点为止
如果发现无前驱的顶点，可以说明图中存在环。 伪代码实现：
Status TopologicalSort(ALGraph G) {
// 有向图G采用邻接表存储结构。
// 若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则ERROR。
SqStack S;
int count,k,i;
ArcNode *p;
char indegree[MAX_VERTEX_NUM];
FindInDegree(G, indegree); // 对各顶点求入度indegree[0..vernum-1]
InitStack(S);
for (i=0; i<G.vexnum; ++i) // 建零入度顶点栈S
if (!indegree[i]) Push(S, i); // 入度为0者进栈
count = 0; // 对输出顶点计数
while (!StackEmpty(S)) {
Pop(S, i);
printf(i, G.vertices[i].data); ++count; // 输出i号顶点并计数
for (p=G.vertices[i].firstarc; p; p=p->nextarc) {
k = p->adjvex; // 对i号顶点的每个邻接点的入度减1
if (!(--indegree[k])) Push(S, k); // 若入度减为0，则入栈
}
}
if (count<G.vexnum) return ERROR; // 该有向图有回路
else return OK;
} // TopologicalSort
