可能重复:用于检测有向图中的循环的最佳算法
我正在寻找一种算法来在有向图中找到循环 .
我的图表只在节点中有标签,而不是在边缘,它可以变得非常大 .
算法的输出应该是作为一组列表的循环,每个列表应该包含循环中涉及的节点的标签,因此,列表中的第一个和最后一个元素应该是相同的 .
我正在使用的图表很可能只有一个连接组件,没有强连接组件 . 预计周期数会很少(我仍然需要检查) .
对于这个或类似的东西,任何好的算法都是受欢迎的 .
非常感谢你 .
PS:如果事情不明确,请随时向我询问更多细节,例如,图表被存储(到目前为止)为一组边缘,从一个节点到几个节点,通常是一个,这应该是无关紧要的,恕我直言 .
1 回答
一个类似的问题已经被问到,有人提供了一个非常详细的答案,可能会帮助你 - Finding all cycles in a directed graph