将有向无环图转换为序列的算法

Question

如果 D 依赖于 B，而 C 又依赖于 A，我希望得到 ABCD(或 ACBD)；即从图中生成一个平面序列，使得所有节点都出现在它们的任何后代之前。例如，我们可能需要在安装 X 之前安装 X 的依赖。

对此有什么好的算法？

Answer 1

在这样的问题中，术语对于找到正确的链接至关重要。

您描述的依赖项形成一个 partially ordered set (首字母)。简单地说，这是一个带有顺序运算符的集合，其中一些对的比较可能是未定义的。在您的示例中，B 和 C 是不可比的(B 既不依赖于 C，也不依赖于 C 依赖于 B)。

顺序运算符的扩展是尊重原始部分顺序并为以前无法​​比较的元素添加一些额外比较的运算符。在极端情况下:线性扩展 导致总排序。对于每个部分排序 such an extension exists .

从偏序集中获得线性扩展的算法称为 topological sorting .维基百科提供了以下非常简单的algorithm :

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)