Joh*_*ton 15 algorithm graph-theory depth-first-search
我需要使用DFS在有向图中找到最长的周期.
我曾经看过这篇维基百科的文章描述了这样做的方式,我认为它解决了这个问题,例如用以下三种状态之一标记节点:节点尚未访问,完成搜索节点,节点访问,但尚未完成访问.
如果有人能与我分享链接,我将不胜感激.顺便说一句,它不是Tarjan的算法.
下面的问题是我想要解决的问题,如果你想知道的话.
在第一行中给出的两个数字是N和M,每个数字表示节点的数量和有向边的数量.
从第二行给出M组两个数字A和B,这意味着节点A和B连接但您只能遍历从A到B的节点.
input.txt中:
7 9
1 2
2 3
3 1
3 4
4 5
5 1
5 6
6 7
7 2
在这种情况下,答案是6,因为2> 3> 4> 5> 6> 7> 2.
我认为最长的基本周期(或电路)是比最长周期更好的术语.
无论如何,这个pdf可能会有所帮助:查找有向图的所有基本电路
这个有一年历史的stackoverflow问题还有许多相关问题和算法的链接: 查找有向图中的所有周期