排序由連接

節點圖我有下面的圖片排序由連接

一個節點圖類似，我想通過各級節點進行排序。所以像

[8, 4, 5, 9, 3, 1, 2, 7 , 6, 10]

當我構造的節點和連接，他們可以以任何順序。像

class Element: 
    def __init__(self, name): 
     self.name = name 

class ElementConnection: 
    def __init__(self, element_source, element_dest): 
     self.element_source = element_source 
     self.element_dest = element_dest 



element5 = Element("Element5") 
element3 = Element("Element3") 
element1 = Element("Element1") 
element2 = Element("Element2") 
element8 = Element("Element8") 
element9 = Element("Element9") 
element7 = Element("Element7") 
element4 = Element("Element4") 
element10 = Element("Element10") 

elements = [element5, element3, element1, element2, element8, element10, element9, element7, element4] 

connections = [ 
       ElementConnection(element8, element5), 
       ElementConnection(element4, element3), 
       ElementConnection(element9, element2), 
       ElementConnection(element9, element7), 
       ElementConnection(element5, element7), 
       ElementConnection(element4, element9), 
       ElementConnection(element2, element6), 
       ElementConnection(element3, element1), 
       ElementConnection(element6, element10), 
       ElementConnection(element1, element10), 
       ]

所以，我想使用連接列表排序元素列表。有沒有達到此目標的標準方法？

感謝

來源

2017-06-14 Glenn Pierce

你描述的是[*拓撲排序*]（https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm）。 –

如果這不是一個學習練習，我會建議調查NetworkX庫，而不是重新發明輪子。例如，請參見其[拓撲排序]的文檔（https://networkx.github.io/documentation/networkx-1.9/reference/generated/networkx.algorithms.dag.topological_sort.html）。 –

這不是一個學習練習。我沒有意識到算法的名字。我的主要代碼是在Rust中，但我已經簡化它在Python中進行實驗。 –

我覺得你可以考慮breadth first search算法的圖形。這不是關於任何類型的「排序」，但您可以獲得所需的切片。你可以通過上面的鏈接得到這個算法的描述（這是一個樹的例子）。

來源

2017-06-14 08:44:33 Dmitry

接受這個，因爲它似乎工作得很好，並且是廣度優先搜索的第一個答案。 –

回答

相關問題