[SOLVED] Is there a difference between dfs and topological sort? Can topological ordering be achieved without using dfs?

Is there a difference between dfs and topological sort? Can topological ordering be achieved without using dfs?

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?

Solution

Well, topological sorting is a specific order of the nodes of a directed acyclic graph, which can be calculated by depth-first search. Besides depth-first search, there are other methods to find a valid order, like the Kahn's algorighm.

Note that a DAG might have many valid topological orders (not restricted to one). This means that one implementation of DFS can yield one (valid) order, while another DFS implementation (in which the nodes are selected by a different heuristic) can yield another order.

Consider this DAG:

  3 ← 1 → 2

A valid order can be 1 2 3, but also 1 3 2. When running DFS, on each step the implementation might select different nodes, depending on certain criteria (heuristics), and thus the resulting order can be different.