將有向無環圖轉換爲序列的算法

Question

如果D依賴於每個都依賴於A的B和C，我想要ABCD（或ACBD）作爲結果;那就是從圖中產生一個平坦的序列，使得所有節點出現在它們的任何後代之前。例如，在安裝X之前，我們可能需要安裝X的依賴項。

這是什麼算法？

Answer 1

在這樣的問題中，術語對於找到正確的鏈接至關重要。

您描述的依賴關係形成partially ordered set（poset）。簡而言之，這是一個帶有順序操作符的集合，對此，某些對的比較可能未定義。在您的示例中，B和C不兼容（B取決於C，也不取決於B取決於C）。

擴展是一種尊重原始部分順序並添加一些額外比較到先前不可比較元素的順序運算符。在極端情況下：線性擴展導致總體排序。對於每個部分訂購such an extension exists。

從poset獲得線性擴展的算法被稱爲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)