具有循环依赖性检测的依赖性排序
在你开始向我扔维基百科和博客的链接之前，请听我说完。
我正在尝试找到最佳算法/函数来对......东西进行依赖排序。每个项目都有一个其依赖项的列表。
我想要一些基于迭代器的东西，但这并不是很重要。
重要的是算法准确指出哪些项是依赖循环的一部分。我想提供这种情况下的详细错误信息。
实际上，我正在考虑从“依赖节点”类中对我的项目进行子类化，该类具有完成工作所需的布尔值/函数。欢迎使用很酷（但具有描述性）的名称:)
Before you start throwing links to wikipedia and blogs in my face, please hear me out.
I'm trying to find the optimal algorithm/function to do a dependency sort on... stuff. Each item has a list of its dependencies.
I would like to have something iterator-based, but that's not very important.
What is important is that the algorithm points out exactly which items are part of the dependency cycle. I'd like to give detailed error information in this case.
Practically, I'm thinking of subclassing my items from a "dependency node" class, which has the necessary booleans/functions to get the job done. Cool (but descriptive) names are welcome :)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
它通常称为拓扑排序。大多数书籍/论文/任何涉及拓扑的内容当然，排序也将涵盖循环检测。
It's normally called a topological sort. Most books/papers/whatever that cover topological sorting will also cover cycle detection as a matter of course.
我完全不明白为什么很难找到依赖循环（如果有的话）！你只需要检查是否有任何你已经通过的节点，同时应用 bfs 算法来找出所有的依赖关系。如果有的话，你只需回滚你下来的方式，重新向上访问一个节点，并标记所有节点，直到到达指定节点的第一次访问。您通行证中的所有内容都将被标记为一个循环。 （只需发表评论，如果您需要，我会提供代码来做到这一点）
I don't exactly get why is it so hard to find the dependecy cycle if there is any! you just have to check if there is any node you already passed over while appling bfs algorithm to find out all the dependecies. if there is one you just roll back the way you came down to revisit a node alll the way up and mark all the nodes until you reach the first visit at the specified node. all the ones in your pass will be marked as a cycle. (just leave a comment and i'll give a code to do that if you need)