如何基於依賴性進行排序？

Question

我有一個類有一個「依賴關係」列表指向其他類相同的基本類型。

class Foo(Base): 
    dependencies = [] 

class Bar(Base): 
    dependencies = [Foo] 

class Baz(Base): 
    dependencies = [Bar] 

我想排序這些類生成的實例基於它們的依賴關係。在我的例子中，我希望Foo的實例先來，然後是Bar，然後是Baz。

排序的最佳方法是什麼？

Answer 1

它被稱爲拓撲排序。

def sort_deps(objs): 
    queue = [objs with no dependencies] 
    while queue: 
     obj = queue.pop() 
     yield obj 
     for obj in objs: 
      if dependencies are now satisfied: 
       queue.append(obj) 
    if not all dependencies are satisfied: 
     error 
    return result 

Answer 2

上週我有一個類似的問題 - 希望我會知道堆棧溢出，然後！我一直在尋找，直到我意識到我有一個DAG（定向非循環圖，因爲我的依賴關係不能遞歸或循環）。然後我找到了幾個算法的參考來對它們進行排序。我使用深度優先遍歷來到葉節點並首先將它們添加到排序列表中。

這裏有一個頁面，我發現有用：

Directed Acyclic Graphs