0

The problem is: given a directed graph, find the longest simple cycle in the graph. I've searched the question and found this link Finding the longest cycle in a directed graph using DFS. The answer explains this is an NP hard problem.

But I'm confused by the following algorithm, it seems to run in O(|V| + |E|) time because we visit each edge exactly once.

maintain the following variables:

(1) global max: the length of the longest cycle in the graph.
(2) Map<GraphNode, Integer> cache: stores length of the longest cycle starting from the key node.
(3) Map<GraphNode, Integer> pathVisited: stores the node visited on the path and the corresponding step number. For example, A -> B -> C -> A, if starts from A, the Map will look like {A -> 1, B -> 2, C -> 3}, and when enters A again, the step becomes 4, and thus the length of cycle is 4 - 1 = 3
(4)Set<GraphNode> visited: contains the graphNodes that have been fully explored.

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)

I feel the above algorithm can solve the problem in O(|V| + |E|) time, because after fully exploring one node, we won't start dfs on that node again.

Can anyone give me some hint on why the above algorithm is wrong?

lastr2d2
  • 3,604
  • 2
  • 22
  • 37
Patrick
  • 555
  • 1
  • 6
  • 25

2 Answers2

1

Consider the following graph:

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

Now, imagine you start your DFS at node A and visit the nodes in the order B, then C, then D, and then E. Unless I've misinterpreted what your code is doing, I don't believe that this visitation order will allow you to discover the longest cycle A, B, C, E, D, A, since once you've visited D you've assigned it the wrong depth and cut off the path back to A.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • Thanks for the answer! Just to make sure, the algorithm is wrong in this case because the longest cycle should be of length 5 (A -> B-> C -> E -> D -> A), however, if we visit the graph in the order A->B->D->E, i.e. visit D before E, then via E we will not be able to go back to A because D has been fully explored, so never get the correct answer. – Patrick Dec 20 '18 at 19:09
0

I think problem is what is "elementary cycle". DFS is good if cycle have all point visited once time. But This is problem:

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

Assume direction:

A -> B

B -> D,E

C -> D

D -> E,A

E -> C

DFS will find longest cycle is 5, A->B->E->C->D->A but longest cycle should be A->B->E->C->D->E->A. Maybe you should try with new view

Hai
  • 73
  • 1
  • 10