按连接对节点图排序

Question

我有一个节点图，如下图所示

我想按级别对节点进行排序。比如说

[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),
              ]

所以我想用连接列表对元素列表进行排序。 有没有一个标准的方法来实现这一点？你知道吗

谢谢

Answer 1

我想你可以考虑一个图的breadth first search算法。它不是关于任何类型的“排序”，但您可以获得所需的切片。 你可以通过上面的链接得到这个算法的描述（这是树的一个例子）。你知道吗