排序由连接

节点图我有下面的图片排序由连接

一个节点图类似，我想通过各级节点进行排序。所以像

[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

接受这个，因为它似乎工作得很好，并且是广度优先搜索的第一个答案。 –

回答

相关问题