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

Help Needed in Cycle Detection in Graphs
Автор catismyfav, история, 5 лет назад, По-английски

Hello all! I have started studying dfs and it's applications and I was studying topological sorting (https://www.spoj.com/problems/TOPOSORT/). I am stuck at the part to check the graph is Acyclic or not? Can anyone help with any easier way to check this? Thanks!

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

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

I think Kahn's algorithm will be the easiest.

kahn's algorithm : https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/

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

Assuming that your topological sorting algorithm terminates regardless of whether the graph is acyclic, you can generate an ordering with the algorithm, and then just check if it's valid. If the ordering is invalid (a node is added before one of its parents), then it has cycles.

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

    How to check if ordering is valid?

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

      If the ordering is invalid (a node is added before one of its parents), then it has cycles.

      I said it in my previous comment.

      But also, some algorithms will instead produce an ordering that doesn't contain all of the nodes. It really depends on what algorithm you use.

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

Code

→ Ответить