Алгоритм Задача: Найти самый длинный элементарный цикл в ориентированном графе

Question

Проблема в том, что для заданного графа найдите самый длинный простой цикл в графе.Я искал вопрос и нашел эту ссылку Нахождение самого длинного цикла в ориентированном графе с использованием DFS .Ответ объясняет, что это трудная проблема NP.

Но меня смущает следующий алгоритм, который, кажется, работает за O (| V | + | E |), потому что мы посещаем каждый край ровно один раз.

поддерживает следующие переменные:

(1) global max: длина самого длинного цикла на графике.
(2) Map<GraphNode, Integer> cache: хранит длину самого длинного цикланачиная с ключевого узла.
(3) Map<GraphNode, Integer> pathVisited: сохраняет посещенный узел на пути и соответствующий номер шага.Например, A -> B -> C -> A, если начинается с A, карта будет выглядеть как {A -> 1, B -> 2, C -> 3}, а когда снова входит в A, шаг становится4, и, следовательно, длина цикла составляет 4 - 1 = 3
(4) Set<GraphNode> visited: содержит полностью изученные узлы graph.

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

Мне кажется, проблема в том, что такое «элементарный цикл».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-> B-> E-> C-> D-> E-> A.Может быть, вам стоит попробовать с новым видом

Answer 2

Рассмотрим следующий график:

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

Теперь представьте, что вы запускаете DFS на узле A и посещаете узлы в порядке B, затем C, затем D и затем E. Если у меня нетневерно истолковав, что делает ваш код, я не верю, что этот порядок посещений позволит вам обнаружить самый длинный цикл A, B, C, E, D, A, поскольку, посетив D, вы ошиблисьГлубина и отрезать путь обратно к А.