<p style="box-sizing:inherit;color:rgba(0&#44; 0&#44; 0&#44; 0.87);font-family:&quot;font-size:19.2px;text-wrap:wrap;background-color:#FFFFFF;">
https://oi-wiki.org/graph/topo/

拓扑排序（Topological sorting）要解决的问题是如何给一个有向无环图的所有节点排序。

我们可以拿大学每学期排课的例子来描述这个过程，比如学习大学课程中有：「程序设计」，「算法语言」，「高等数学」，「离散数学」，「编译技术」，「普通物理」，「数据结构」，「数据库系统」等。按照例子中的排课，当我们想要学习「数据结构」的时候，就必须先学会「离散数学」，学习完这门课后就获得了学习「编译技术」的前置条件。当然，「编译技术」还有一个更加前的课程「算法语言」。这些课程就相当于几个顶点 , 顶点之间的有向边  就相当于学习课程的顺序。教务处安排这些课程，使得在逻辑关系符合的情况下排出课表，就是拓扑排序的过程。

但是如果某一天排课的老师打瞌睡了，说想要学习 数据结构，还得先学 操作系统，而 操作系统 的前置课程又是 数据结构，那么到底应该先学哪一个（不考虑同时学习的情况）？在这里，数据结构 和 操作系统 间就出现了一个环，显然同学们现在没办法弄清楚自己需要先学什么了，也就没办法进行拓扑排序了。因为如果有向图中存在环路，那么我们就没办法进行拓扑排序。

因此我们可以说 在一个 DAG（有向无环图） 中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点  到  的有向边 , 都可以有  在  的前面。

还有给定一个 DAG，如果从  到  有边，则认为  依赖于 。如果  到  有路径（ 可达 ），则称  间接依赖于 。

拓扑排序的目标是将所有节点排序，使得排在前面的节点不能依赖于排在后面的节点。