MedoN11's blog

By MedoN11, history, 9 years ago, In English

Yes, I know there is a simple detection algorithm using DFS, but assume for a certain application, I'm interesting in doing via breadth first search traversal, is it possible to do so? I've only seen confirmations about that on quora but without psuedo code or any details.

What is the most efficient way to do so? and if possible, can someone please supply a code? ( A simple short pseudo code is enough).

Thanks.

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

| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It can be also done with breadth first topological sort. If we have can't sort the graph topologically, then the graph has a cycle. http://mirror.codeforces.com/contest/512/submission/9683156

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

    Hello, Are there two kind of toposort ?And if yes only breadth first toposort will be able to detect cycle not dfs please clarify,sir?