给定一个有向图，我需要一种方法来检测图中的环路，以及确定顶点是否在环路中，或者是否只与环路中的一个顶点有边。
这是一个例子:
A -> B
B -> A
C -> A
在这种情况下，A -> B 和 B -> A 形成一个循环，应该以一种方式着色，但是顶点 C 不是循环的一部分，它只是进入循环的边缘，所以它应该以不同的方式着色。
我可以轻松地自己检测循环，只需从一个随机顶点开始，对其着色，然后进行 DFS。如果我碰到一个具有相同颜色的顶点，我知道我处于一个循环中并且会递归地将错误传回。问题是它不允许我查看我从递归调用中得到的错误是因为我当前处于循环中，还是因为我只是指向之前检测到的错误。
该图基本上表示延迟评估单元格的依赖关系，我试图查看一个单元格是否因为传递引用自身而未能评估，或者因为它依赖于循环中的其他一些单元格(这两个应该是不同的错误。)
我现在实现它的方式是，我只是强制对当前单元格的所有依赖项进行评估，并根据评估结果分配值。但如前所述，这种递归不允许我区分这两种情况。
最佳答案
用于搜索有向图强连通分量的 Tarjan 算法 http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm允许您做出所需的区分。
关于algorithm - 检测有向依赖图中的循环并检测顶点是循环的一部分还是仅依赖于一个顶点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27203613/