算法问题：在有向图中找到最长的基本循环

Question

问题是：给定一个有向图，找出图中最长的简单环。我搜索了这个问题并找到了这个 link Finding the longest cycle in a directed graph using DFS。答案说明这是一个NP难题。

但是我对下面的算法感到困惑，它似乎在 O(|V| + |E|) 时间内运行因为我们只访问了每条边一次。

维护以下变量：

(1) global max:图中最长循环的长度。
(2) Map<GraphNode, Integer> cache：存储从关键节点开始的最长循环的长度。
(3)Map<GraphNode, Integer> pathVisited：存储路径上访问过的节点和对应的步数。比如A -> B -> C -> A，如果从A开始，Map会变成{A -> 1, B -> 2, C -> 3}，再次进入A时，step变成4, 因此循环长度为 4 - 1 = 3
(4)Set<GraphNode> visited: 包含已经完全探索的graphNodes。

dfs(GraphNode cur, int curStep, Set<GraphNode> visited, Map<GraphNode, Integer> cache, Map<GraphNode, Integer> pathVisited):
    if visited.containsKey(cur), then 
        return // if the node have been explored, no need to explore again
    // if see a cycle, update the results(cache)
    if pathVisited.containsKey(cur), then 
       newCycleLen = curStep - pathVisited.get(cur)
       cache.put(cur, max {newCycleLen, cache.get(cur)})
       return 
    // no cycle yet, continue the search
    pathVisited.put(cur, curStep)
    for each neighbor of cur:
       dfs(neighbor, curStep + 1, cache, pathVisited)
    endfor
    visited.add(cur); // current node have been explored, in the future no need to visit it again.
    path.remove(cur)

我感觉上面的算法可以在O(|V| + |E|)时间内解决问题，因为完全探索完一个节点后，我们就不会再在该节点上启动dfs了。

谁能给我一些提示，说明为什么上面的算法是错误的？

Answer 1

考虑下图：

     D -- A
   / |    |
  E  |    |
   \ |    |
     C -- B

现在，假设您在节点 A 开始 DFS 并按顺序访问节点 B，然后是 C，然后是 D，然后是 E。除非我误解了您的代码在做什么，否则我不相信这个访问顺序将允许你发现最长的循环 A、B、C、E、D、A，因为一旦你访问了 D，你就给它分配了错误的深度并切断了返回 A 的路径。

Answer 2

我认为问题是 "elementary cycle"。如果循环所有点都访问一次，则 DFS 很好。但这是个问题：

A---B
|\ /|
| E |
|/ \|
C---D

假定方向：

A -> B

B -> D,E

C -> D

D -> E,A

E -> C

DFS会发现最长的循环是5，A->B->E->C->D->A 但最长的循环应该是A->B->E->C->D->E ->A。也许你应该尝试使用新视图

算法问题：在有向图中找到最长的基本循环

Algorithm Problem: Find the longest elementary cycle in a directed graph

algorithm

graph

depth-first-search

np