拓扑排序，是数据结构与算法中图论部分的经典概念，也是软考中级软件设计师、高级系统架构设计师考试中反复出现的考点。按照教材与算法导论中的标准表述，拓扑排序指的是：对一个有向无环图（Directed Acyclic Graph，简称 DAG）中的所有顶点，排出一个线性序列，使得对于图中任意一条从顶点 u 指向顶点 v 的有向边，u 在这个序列中都一定排在 v 的前面。这个满足"前驱在前、后继在后"约束的线性序列，就叫做该有向无环图的一个拓扑序列。
理解这个定义，需要把握三个关键词。第一个关键词是有向图。拓扑排序处理的对象必须是有向图，因为只有有向边才具有方向性，才能表达"谁先谁后"的次序关系；无向图的边没有方向，无法确定顶点之间的先后，拓扑排序也就失去了意义。第二个关键词是无环。有向图中若存在环，环上顶点互为前驱和后继，形成循环依赖，任何一个顶点都无法被合理地安排在另一个顶点前面，拓扑排序必然失败。第三个关键词是线性序列。拓扑排序的结果是一个一维的线性排列，它把原本网状结构的依赖关系压缩成一条直线，使所有依赖约束都能被满足。
为更准确把握拓扑排序的实质，有必要引入两个紧密相关的专业术语，它们也是软考选择题和案例分析的常见命题素材。第一个术语是偏序与全序。偏序关系指集合中只有部分元素之间可以比较先后，全序关系则指任意两个元素之间都能比较先后。拓扑排序的本质，就是把有向无环图所表达的偏序关系扩展成全序关系，把原来只能部分比较的顶点排成任意两个都可比较先后的线性序列。这个"偏序转全序"的视角，是理解拓扑排序数学本质的关键，命题人常围绕它设置概念辨析题。
第二个术语是 AOV 网，即用顶点表示活动（Activity On Vertex）的网络。在 AOV 网中，每个顶点代表一项活动，每条有向边代表活动之间的先后约束：若有向边从顶点 u 指向顶点 v，就表示活动 u 必须先于活动 v 完成。例如"数据结构"课程要求先修"C 语言"，AOV 网中就从"C 语言"引出一条有向边指向"数据结构"，对整个课程体系执行拓扑排序，就能得到合理的修课顺序。AOV 网是拓扑排序最经典的应用载体，它与 AOE 网（用边表示活动的网络）共同构成软考图论应用部分的两大支柱，二者区别与联系是高频易错点，后文会专门辨析。
要真正理解拓扑排序，必须回到它的数学本质。拓扑排序要求每个顶点都排在它所有后继之前，同时又排在其所有前驱之后。设想一个有向图中存在一个环，由顶点 v1、v2、v3 依次首尾相连构成。按照定义，边 v1 指向 v2 要求 v1 排在 v2 之前，边 v2 指向 v3 要求 v2 排在 v3 之前，边 v3 又指回 v1 要求 v3 排在 v1 之前。把这三条约束连起来看，就得到"v1 在 v2 前、v2 在 v3 前、v3 又在 v1 前"的矛盾链条，这在逻辑上无法同时满足。
这个矛盾的本质，在于环导致了循环依赖，而循环依赖在先后次序的世界里不可解。拓扑排序的输出是线性的全序排列，任何线性排列都必须满足反对称性：若 a 排在 b 之前，则 b 不可能排在 a 之前。环的存在恰恰要求 a 既在 b 之前、又要在 b 之后，直接违背线性次序的基本公理。因此只要图中存在环，无论采用何种算法，拓扑排序都无法产生合法结果。软考命题人非常喜欢考察这一点，常见形式是给出一张图，让考生判断它能否进行拓扑排序，或判断某个给定顶点序列是否是该图的拓扑序列，而陷阱往往藏在"图中有环"这个隐蔽条件里。
进一步深挖，环的存在还会导致算法层面出现一个可观测的"症状"：算法无法处理完所有顶点。以入度为核心的拓扑排序算法，每处理完一个顶点，就把它从图中删除，并将其所有后继顶点的入度减一。若图中有环，环上顶点的入度永远无法降为零，因为它们相互构成封闭的依赖圈，谁也等不到前驱被处理的那一天。于是算法会在还剩若干顶点未处理时提前终止，输出顶点数目小于顶点总数。这个"输出顶点数少于顶点总数即可判定有环"的技巧，是拓扑排序判环的核心方法，也是考试中判断一个图是否有环的经典手段。
理解拓扑排序算法，绕不开两个最基础的图论概念：入度与出度。入度指以某顶点为终点的有向边数目，即"有多少条边指向它"；出度指以某顶点为起点的有向边数目，即"从它发出多少条边"。在 AOV 网的语义下，一个顶点的入度代表这项活动还剩多少个前置活动未完成；入度为零，意味着它的所有前驱都已被满足，已具备开始执行的条件，可以立即被安排进拓扑序列。
拓扑排序的核心逻辑，正是围绕入度为零展开的。算法每一步都从图中当前入度为零的顶点中挑选一个加入结果序列，然后把它连同它发出的所有边一起从图中删除，同时把所有直接后继顶点的入度各减一。这个删除操作模拟了"完成一项活动"的语义：活动完成后，其后继活动所依赖的前置条件就少了一个。随着算法推进，图中会不断有新的顶点入度降为零，成为下一轮可处理的候选，直到所有顶点处理完毕，或找不到入度为零的顶点为止。
入度与出度看似简单，却是命题人设置计算题和概念题的重要抓手。常见问法包括：给定 AOV 网，求某顶点的入度和出度；给定邻接矩阵，统计某行非零元素个数求出度、某列非零元素个数求入度；或给定入度出度序列，判断是否是有向无环图可能的度序列。理解入度与出度在邻接矩阵中的几何对应关系，是解题关键：在邻接矩阵表示法中，第 i 行非零元素个数是顶点 i 的出度，第 i 列非零元素个数是顶点 i 的入度，这一对应关系在软考存储结构计算题中反复出现。
拓扑排序的第一个经典实现是卡恩算法，它以入度统计为基础，本质上是一种广度优先的贪心策略。第一步，扫描整张图，统计每个顶点入度，把所有入度为零的顶点收集进候选集合。第二步，从候选集合取出一个入度为零的顶点，加入拓扑序列结果末尾。第三步，遍历这个顶点的所有直接后继，把每个后继的入度减一，若某后继入度因此降到零，就把它加入候选集合。第四步，重复第二、三步，直到候选集合为空。
算法结束时需做关键的判环检查：若已加入拓扑序列的顶点数目等于顶点总数，说明图中无环，拓扑排序成功；若少于顶点总数，说明图中一定存在环，拓扑排序失败。这个判环检查正是卡恩算法的点睛之笔，它把"能否拓扑排序"这个抽象问题，转化成可直接观察计数的操作。卡恩算法的时间复杂度为顶点数加边数的线性量级，因为每条边恰好被访问一次用于将终点入度减一，每个顶点也只处理一次。
卡恩算法的"广度优先"属性，体现在它从入度为零集合取顶点的顺序上。若用队列维护候选集合，算法会按顶点入度降为零的先后次序处理它们，呈现类似广度优先搜索的逐层推进特征。由此引出一个软考重要推论：一个 AOV 网的拓扑序列通常不唯一，不同取顶点顺序会得到不同合法拓扑序列。当候选集合同时存在多个入度为零的顶点时，取任意一个都满足定义，这也解释了同一张图为何能对应多个拓扑序列。
拓扑排序的第二个经典实现，是基于深度优先遍历的后序反转方法。它与卡恩算法从"前驱"入手的视角完全不同，而是从"后继"切入。深度优先遍历有一个重要性质：当搜索从某顶点出发，递归访问完它所有后代、准备回溯离开时，这个顶点所有的后继都已在它之前"访问完成"。若把顶点"访问完成"的时刻记录下来，得到完成时刻的先后次序，再整体反转，恰好满足拓扑序列要求——完成得越晚的顶点，其依赖越靠前。
具体而言，深度优先遍历会沿着有向边方向一路深入，每访问到一个顶点就标记为已访问，当它没有任何未访问的后继可深入时，就把它压入栈中然后回溯。遍历结束后，栈中自底向上的顶点次序就是图的一个拓扑序列，因为深度优先搜索的后进先出特性，恰好保证"先完成的后进栈、后完成的先进栈"，而先完成的顶点正是依赖链上更靠后的顶点。整个过程依赖"无环"这个前提——正因没有环，深度优先搜索才不会陷入无限递归。
从后序反转法可引出一个软考常考结论：对有向无环图执行深度优先遍历，若存在从 u 到 v 的路径，那么在完成时刻序列中，v 的完成时刻一定早于 u。这个结论是后序反转法正确性的理论基础，命题人常以判断题或概念题考察。卡恩算法直观易懂、判环方便，后序反转法利用递归的天然结构、实现简洁，二者都是软考的原理性考点，考生应把两种思路都吃透。
拓扑排序之所以是软考数据结构部分的常客，是因为它在现实工程与软件系统中应用极广。最经典的应用场景是课程表编排。大学里很多课程存在先修关系，比如学"编译原理"前必须先修"数据结构和算法"，学"数据结构"前又必须先修"程序设计基础"。把所有课程及其先修关系建模成 AOV 网，执行拓扑排序就能得到满足所有先修约束的合理修课顺序。这个场景几乎是所有数据结构教材引
本篇完！