Блог пользователя Parvej

Finding all the simple cycles in an undirected graph.
Автор Parvej, история, 4 года назад, По-английски

How can I find all the simple cycles in an undirected graph?

126615260_419079712777006_8560932289449234104_n.png In the picture, there are 3 simple cycle:

  1. 1-2-3

  2. 1-2-4-5

  3. 1-3-2-4-5

How can I print all of them?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Parvej (previous revision, new revision, compare).

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Just try to backtracking/bruteforces. Each vertices during the visit will be marked (not go to that vertice again), else unmark it. The complexity will be $$$O(n!)$$$ time

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    SPyofgame I think time complexity will be O ((N^2) * (N!)) as for each path there will be N^2 computation right? Correct me if I am wrong. Thanks in advance.

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I dont think we need $$$O(n^2)$$$ for each $$$O(n!)$$$ path since you can try to implement directly or something similar.

      By the way, $$$O(n^2)$$$ is also considerably small compared to $$$O(n!)$$$. So unless the time limit is small, you can try to improve the complexity by changing implementation or even a bit of heuristic — which can provide better complexity and constant.

      → Ответить