I was trying to write code for detecting a cycle in a directed graph and if there is no cycle then return a topological order of the same.
While I was searching for it I came across different techniques like DFS and topological sorting to detect cycle in a directed graph.
Is there any difference between these two?
Well, topological sorting is a specific order of the nodes of a directed acyclic graph, which can be achieved by depth-first search. Besides depth-first search, there are other methods to find the topological order, like the Kahn's algorighm.
Topological sort is a DFS-based algorithm on a directed acyclic graph (DAG). Topological ordering is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering.
A topological ordering is possible if and only if the graph has no directed cycles. But DFS can be performed on directed or undirected graphs.
Topological sort uses DFS in the following manner:
Run-time: O(V+E)
By nature, the topological sort algorithm uses DFS on a DAG. The DFS properties are crucial for the returned list to appear in correct, topological order. However, as seen in the answers above, yes ordering cannot be achieved without using DFS. Examples are Kahn's algorithm and parallel sorting.
If you want to get a clear idea, you can try the following problem.
At first, you might jump into doing straightforward DFS, but it fails in some cases.
For eg: DFS fails in the following test case:
5 4 (no. of vertices and edges respectively)
(Description of the edges)
1 2
2 3
1 4
4 3
