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.
Auto comment: topic has been updated by MedoN11 (previous revision, new revision, compare).
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
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?
Any algorithm that tries to find a top sort can detect cycles — the vertices can be topsorted if and only if there is no cycle in the graph. It can be done in both depth and breadth first manner, here is a nice explanaition for DFS topsort, my solution above is using BFS. http://www.cse.ust.hk/faculty/golin/COMP271Sp03/Notes/MyL08.pdf