catismyfav's blog

Help Needed in Cycle Detection in Graphs
By catismyfav, history, 5 years ago, In English

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!

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I think Kahn's algorithm will be the easiest.

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

→ Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to check if ordering is valid?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Code

→ Reply