如何根据依赖关系进行排序？

Question

如何根据依赖关系进行排序？

我有一个类,它有一个"依赖项"列表,指向同一基类型的其他类.

class Foo(Base):
    dependencies = []

class Bar(Base):
    dependencies = [Foo]

class Baz(Base):
    dependencies = [Bar]

Run Code Online (Sandbox Code Playgroud)

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

排序这个的最佳方法是什么？

Answer 1

Die*_*Epp 18

它被称为拓扑排序.

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

Run Code Online (Sandbox Code Playgroud)

@sleepycal：如果你假装不明白某些事情而表现得粗鲁，那么你就会融入这个网站上的人们，并提出合理的问题。您可能希望查看：http://stackoverflow.com/help/be-nice（特别是，查看第 3 项下的第一个项目符号点，以及该项目符号点末尾括号中的第一个示例.) (4认同)
@sleepycal：该网站是为了回答问题，而不是为您的问题提供完整的解决方案。 (3认同)
@sleepycal：我使用了一种叫做[伪代码]（https://en.wikipedia.org/wiki/Pseudocode）的东西。伪代码实际上并不应该起作用，它只是说明了算法如何在高层次上工作。如果您在理解此答案或填写详细信息时遇到问题，请随时提出问题，我可以为您提供帮助。Stack Overflow 不是一个合约编程网站，我们来这里是为了分享知识，而不是为您编写代码。如果您不确定社区标准，请访问 https://meta.stackoverflow.com (3认同)
@sleepycal：您可以识别伪代码，因为它使用英语短语代替函数，例如“如果现在满足依赖关系”。因为该短语是英语，所以它是伪代码，而不是 Python。您可以在此处查看实际的 Python 代码：https://docs.python.org/3/tutorial/index.html 如果您在理解方面还有任何其他问题，请告诉我。 (3认同)

Answer 2

Cin*_*Joe 5

上周我有一个类似的问题 - 希望我知道Stack Overflow然后!我一直在寻找,直到我意识到我有一个DAG(有向无环图,因为我的依赖关系不能递归或循环).然后我找到了几个算法的引用来对它们进行排序.我使用深度优先遍历来获取叶节点并首先将它们添加到排序列表中.

这是我觉得有用的页面:

有向无环图

有趣......但没有链接到这些其他资源.你能提供一些链接来完成这个问题的答案吗？ (2认同)
我在上面添加了一个链接.作为新的,它只会让我在我的帖子中包含一个,所以这里有另一个有一些好的背景:http://www.codeproject.com/KB/java/BFSDFS.aspx (2认同)

归档时间：	16 年，6 月前
查看次数：	2480 次
最近记录：	16 年，6 月前