如何基于依赖关系进行排序？

Question

我有一个类，它有一个指向其他相同基础类型的类的“依赖项”列表。

class Foo(Base):
    dependencies = []

class Bar(Base):
    dependencies = [Foo]

class Baz(Base):
    dependencies = [Bar]

我想根据它们的依赖关系对这些类生成的实例进行排序。在我的示例中，我希望Foo的实例首先出现，然后是Bar，最后是Baz。

有什么最好的方法可以排序吗？

- Soviut

---

你是在询问Python中的拓扑排序吗？http://en.wikipedia.org/wiki/Topological_sorting - S.Lott

你可能需要寻找“有向图排序”，因为这本质上就是你要做的事情。 - Clinton Pierce

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

- Dietrich Epp

---

这个网站的目的是回答问题，而不是为您提供完整的解决方案。 - Dietrich Epp

那是一个糟糕的论据，你发布了一段无法运行的代码片段。这只是懒惰的表现。 - SleepyCal

我用了一种叫做“伪代码”的东西。伪代码实际上并不会起作用，它只是说明算法在高层次上是如何工作的。如果你对这个答案有困惑或填写详细信息有问题，请随时提问，我可以帮助你。 Stack Overflow 不是一家合同编程网站，我们在这里分享知识，而不是为你编写代码。如果您对社区标准不确定，请前往 https://meta.stackoverflow.com。 - Dietrich Epp

你可以通过英语短语代替函数来识别伪代码，例如“if dependencies are now satisfied”（如果依赖现在得到满足）。由于这个短语是英语，所以它是伪代码而不是Python代码。你可以在这里查看实际的Python代码：https://docs.python.org/3/tutorial/index.html 如果你还有其他理解上的问题，请告诉我。 - Dietrich Epp

如果你故意装作不理解某事而表现粗鲁，那么你将与这个网站上有合法问题要问的人混为一谈。你可能希望阅读：http://stackoverflow.com/help/be-nice （特别是看看第3项下的第一个要点以及该要点末尾括号中的第一个例子）。 - Dietrich Epp

Answer 2

我上周也有一个类似的问题，但很遗憾当时不知道Stack Overflow！我搜索了一下，直到我意识到我有一个DAG（有向无环图），因为我的依赖关系不能是递归或循环的。然后我找到了一些算法参考来对它们进行排序。我使用深度优先遍历来访问叶节点并将它们添加到排序列表中。

这里是我发现有用的页面：

有向无环图

- Cincinnati Joe

---

有趣...但没有这些其他资源的链接。你能提供一些链接来完整回答这个问题吗？ - S.Lott

我在上面添加了一个链接。由于我很新，它只允许我在帖子中包含一个链接，因此这里是另一个具有一些良好背景的链接：http://www.codeproject.com/KB/java/BFSDFS.aspx - Cincinnati Joe

谢谢，你在回答里提供的链接非常好。只是我希望这些大学人士偶尔能插入一张真正的图片，而不是 ANSI 艺术。呵呵 - Soviut