在软考软件设计师、系统架构设计师以及系统分析师的图算法考点中，拓扑排序属于每年必考但分值不高、极易被考生忽视的一类题目。它不考察复杂的公式推导，也不涉及晦涩的数学证明，命题人真正想检验的，是考生能否在有向图的结构之上，准确地理解顶点之间的先后约束关系，并据此排出一个合法的执行顺序。要彻底掌握拓扑排序，必须先从两个最基础的概念谈起。
第一个概念是有向无环图，简称DAG（Directed Acyclic Graph）。图论中的有向图由顶点集合和有向边集合构成，每条边都有明确的方向，从起点指向终点。如果从某个顶点出发，沿着一系列有向边可以最终回到这个顶点本身，那么图中就存在一条有向回路，也就是环。一个有向图若不存在任何有向回路，就称为有向无环图。拓扑排序之所以把研究对象限定在有向无环图之上，是因为一旦图中存在环，顶点之间的先后关系就会陷入循环依赖，根本无法排出一个满足所有约束的线性顺序。
第二个概念是AOV网，即顶点表示活动的网（Activity On Vertex network）。在AOV网中，顶点代表一项活动，有向边代表活动之间的先后依赖关系。比如某门课程是另一门课程的先修课，就用一条从先修课顶点指向后续课顶点的有向边来表示。与之相对的是AOE网，即边表示活动的网（Activity On Edge network），在AOE网中，活动被放置在边上，顶点则代表事件，AOE网主要用于求解关键路径。软考命题人经常把AOV网和AOE网放在同一道题里混淆考生，这是后文常见误区部分要重点展开的内容。
在上述铺垫之后，拓扑排序的正式定义就可以给出：对一个有向无环图的全部顶点进行排序，使得对于图中任意一条从顶点u指向顶点v的有向边，u在排序后的序列中都出现在v之前，这样的线性序列就称为一个拓扑序列，而求出该序列的过程就是拓扑排序。从偏序关系与全序关系的角度看，拓扑排序本质上是把一个集合上的偏序关系转化为全序关系。偏序关系只要求部分元素之间具有可比性，而全序关系要求任意两个元素之间都能比较先后。一个有向无环图刻画的正是一种偏序关系，而拓扑排序要做的，就是把这个偏序关系扩展、整理成一个线性排列，同时不破坏原有的先后约束。
需要特别强调的是，拓扑序列并不是唯一的。一个具有多个入度为零顶点的有向无环图，往往能够产生多个不同的拓扑序列。命题人在考试中常给出四个候选序列，让考生判断哪一个才是合法的拓扑序列，其本质就是在考察考生是否真正理解了"先修关系不可违背"这一核心约束。判断的方法十分朴素：逐条检查图中所有的有向边，确认每条边的起点在序列中都排在终点之前即可。
此外，从教材术语的角度还应当补充一个常被忽略的表述：拓扑排序只对有向无环图有定义，对于有向有环图，它并不能给出一个满足所有约束的线性序列，只能得出"图中存在环"这一结论。因此，严格来说，拓扑排序的存在性等价于图的无环性，这是一个充要条件。考生如果能把这个等价关系理解透彻，那么在遇到"一个有向图能够拓扑排序的前提是什么"这类设问时，就能直接锁定"图中不存在环"这一答案，而不会被"图是连通的""图是强连通的"等干扰项迷惑。
理解拓扑排序的算法机制，必须从入度和出度这两个基础量说起。在有向图中，顶点v的入度是指以v为终点的有向边数量，也就是指向v的边的条数；顶点v的出度是指以v为起点的有向边数量。入度可以直观地理解为"有多少项前置活动还没完成"，出度则可以理解为"这项活动完成之后，会解锁多少项后续活动"。在拓扑排序的语境里，入度为零的顶点具有特殊意义：它没有任何前置依赖，意味着这个顶点所代表的活动可以立即执行。
Kahn算法是最经典、也是软考中最常考的一种拓扑排序算法，它以顶点的入度作为核心依据，采用贪心的思想逐步剥离顶点。这里的"贪心"体现在：算法每一轮都优先选择当前入度为零的顶点，因为入度为零意味着该顶点没有任何前置依赖，无论何时执行都不会破坏约束，这是一种局部最优且能够保证全局正确的选择策略。算法的执行流程可以拆解为以下几个步骤。第一步，统计图中所有顶点的入度，通常用一个入度数组来记录。第二步，找出所有入度为零的顶点，把它们依次放入一个队列或栈中。第三步，从队列或栈中取出一个入度为零的顶点，将其输出到拓扑序列中，同时遍历该顶点的所有出边，把每条出边所指向的邻接顶点的入度减一。这个减一操作的含义非常直观：当前活动已经完成，它所带来的前置依赖随之解除。第四步，若某个邻接顶点在入度减一之后恰好变为零，说明它的所有前置活动都已完成，于是把它加入队列或栈。第五步，重复第三步和第四步，直到队列或栈为空。如果最终输出的顶点数量等于图中的顶点总数，说明图中不存在环，拓扑排序成功完成；如果输出的顶点数量小于顶点总数，说明图中存在环，无法进行拓扑排序。
很多考生只知道"有环就不能拓扑排序"这个结论，却不清楚背后的原理，这恰恰是命题人喜欢深挖的地方。设想图中存在一个环，环上的每个顶点都有一条边指向环上的下一个顶点，这就意味着环上任意一个顶点都要排在其后继顶点之前，而绕环一圈之后又要求最后一个顶点排在第一个顶点之前，于是形成"甲在乙前、乙在丙前、丙又在甲前"的矛盾。用入度的语言来描述：环上的每个顶点都至少有一条入边来自环内，因此它们的入度永远不可能被减到零，Kahn算法最终会因为没有新的入度为零的顶点可用而提前终止，此时输出的顶点数必然小于总数。这正是Kahn算法能够检测有向环的根本原因——它不需要额外的环检测数据结构，只要比较最终输出数量与顶点总数即可。反过来说，如果Kahn算法运行结束后输出的顶点数恰好等于总数，那么可以严格断定图中不存在环，这个结论是可靠且完备的，考生在遇到环检测题时可以直接套用。
Kahn算法的时间复杂度直接取决于图的存储方式，这是软考复杂度类题目的常考细节。若采用邻接矩阵存储，为了统计入度需要扫描整个矩阵，而每取出一个入度为零的顶点后又要遍历矩阵的一整行来寻找其出边，整体时间复杂度会退化到O(V²)。若采用邻接表存储，每个顶点通过链表记录其所有出边邻接点，统计入度只需遍历所有链表一次，取出顶点后也只需沿着该顶点的邻接表逐条处理出边，每条边在算法执行的全过程中只会被访问一次，因此总时间复杂度为O(V+E)。命题人常常在选项中同时给出O(V²)与O(V+E)两个答案，考生必须能够根据存储方式的不同做出正确选择。需要补充的是，这里V代表顶点数，E代表有向边数，在稀疏图中E远小于V²，邻接表的时间优势十分明显，这也是实际工程中普遍采用邻接表存储图的原因。
除了Kahn算法，拓扑排序还可以通过深度优先搜索（DFS）来实现，这种实现方式在理解递归、掌握图遍历时同样具有重要价值。基于DFS的拓扑排序依赖一个关键性质：在有向无环图中，若存在一条从顶点u到顶点v的路径，那么在对图进行深度优先搜索时，u的结束时间一定晚于v的结束时间。所谓结束时间，是指DFS递归遍历完某个顶点及其所有可达顶点之后返回的时刻。基于这一性质，可以设计如下算法：对图中每个尚未访问的顶点执行DFS，在DFS递归返回之前，把当前顶点压入一个栈中。当所有顶点都遍历完成后，栈中的顶点从栈顶到栈底依次弹出，得到的序列就是一个拓扑序列。
DFS法同样具备检测有向环的能力，而且其检测方式与Kahn算法截然不同，命题人偶尔会在这里设置辨析题。在DFS过程中，需要为每个顶点标记三种状态：白色表示尚未访问，灰色表示正在访问（即当前顶点在递归调用栈中），黑色表示已经访问完毕。如果在遍历过程中，某条边指向了一个灰色的顶点，就说明图中存在一条回边，也就是存在环。这是因为指向灰色顶点意味着从当前顶点能够回到一个尚未结束的祖先顶点，形成循环依赖。相比之下，Kahn算法通过计数判断环，DFS算法通过状态颜色判断环，两种方法殊途同归。理解这一区别，有助于考生在遇到"如何判断有向图是否有环"这类问题时，能够从两个角度给出答案。
Kahn算法中，存储入度为零顶点的容器既可以用队列，也可
本篇完！