拓扑排序

在计算机科学中，这种类型的应用出现在指令调度、在电子表格中重新计算公式值时对公式单元格求值的排序、逻辑合成、确定在makefiles中执行的编译任务的顺序、数据序列化以及解决链接器中的符号依赖性等方面。它还用于决定在数据库中以何种顺序加载带有外键的表。

卡恩(1962)首先描述了其中一种算法，它通过选择与最终拓扑排序相同顺序的顶点来工作。首先，找到一个没有引入边的“起始节点”列表，并将它们插入到集合S中；非空无环图中必须至少存在一个这样的节点。然后：

L←包含排序好的元素的空列表S←没有输入边的所有节点的集合whileSisnon-emptydoremoveanodenfromSaddntotailofLforeachnodemwithanedgeefromntomdoremoveedgeefromthegraphifmhasnootherincomingedgestheninsertmintoSifgraphhasedgesthenreturnerror(图表至少有一个环)elsereturnL(拓扑排序的顺序)如果该图是一个DAG，一个解决方案将包含在列表L中(该解决方案不一定是唯一的)。否则，图必须至少有一个环，因此拓扑排序是不可能的。

反映出结果排序的非唯一性，结构S可以是简单的集合、队列或堆栈。根据节点n从集合S中移除的顺序，会生产不同的解决方案。卡恩算法的一个变体在字典上打破了联系，这是科菲曼-格雷厄姆并行调度和分层图形绘制算法的一个关键组成部分。

拓扑排序的另一种算法是基于深度优先搜索。该算法以任意顺序遍历图中的每个节点，启动深度优先搜索，当该搜索到达自拓扑排序开始以来已经被访问过的任何节点或者该节点没有输出边(即叶节点)时终止：

偏序集只是一组对象以及“≤”不等式关系的定义，满足自反性(x≤x)、反对称(如果x≤y和y≤x则x=y)和传递性(如果x≤y和y≤z则x≤z)的公理。一个全序关系是偏序的，如果，对于集合中的每两个对象x和y，x≤y或y≤x。全序关系在计算机科学中一个被人熟知的存在就是需要执行比较排序算法的比较运算符。对于有限集合，全序关系可以用对象的线性序列来标识，其中每当第一个对象在顺序上位于第二个对象之前时，“≤”关系为真；比较排序算法可以用于以这种方式将全序关系转换成序列。偏序的线性扩展和全序相容，也就是说，如果偏序关系中x≤y，那么全序关系中x≤y。

只要存在从x到y的有向路径，也就是说，每当y从x可达时，就可以通过让对象集成为DAG的顶点，并为任意两个顶点x和y定义x≤y为真，来定义任意DAG的偏序；根据这些定义，DAG的拓扑序与这个偏序的线性扩展是一样的。相反，有限集合上的任何偏序都可以定义为DAG中的可达性关系。一种方法是定义一个DAG，该DAG对于部分有序集中的每个对象都有一个顶点，对于x≤y的每对对象都有一个边xy。一般来说，这会产生边较少的Dag，但是这些Dag中的可达性关系仍然是相同的偏序。通过使用这些构造，可以使用拓扑排序算法来寻找偏序的线性扩展。