c++ - 检测循环依赖的依赖排序

Question

在你开始向我扔维基百科和博客的链接之前，请听我说完。

我正在尝试找到最佳算法/函数来对...进行依赖排序。每个项目都有其依赖项的列表。

我想要一些基于迭代器的东西，但这不是很重要。

重要的是该算法准确地指出哪些项目是依赖循环的一部分。在这种情况下，我想提供详细的错误信息。

实际上，我正在考虑从“依赖节点”类中对我的项目进行子类化，该类具有完成工作所需的布尔值/函数。欢迎使用酷（但具有描述性）的名称:)

Answer 1

它通常被称为拓扑排序。当然，大多数涵盖拓扑排序的书籍/论文/任何内容也将涵盖循环检测。

Answer 2

我不完全明白为什么很难找到依赖循环（如果有的话）！您只需要在应用 bfs 算法以找出所有依赖项时检查是否有任何节点已经通过。如果有一个，你只需回滚你下来的方式，一路向上重新访问一个节点并标记所有节点，直到你到达指定节点的第一次访问。您通行证中的所有内容都将被标记为一个循环。（只需发表评论，如果您需要，我会提供代码）