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

Question

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?

Submarine

I also had similar confusion, but now I am clear: DFS: go deeper and deeper along with printing. Topological sort: pick each unvisited vertix and print its dependent first before printing parent(itself). – Chatham

Answer 1

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.

Balkh

So topological sort is just one of the applications of DFS.. right? – Submarine

@DhananjayTyagi Not exclusively. There are multiple approaches for topological sorting. But yes, you can apply DFS in a way to achieve the topological ordering. – Ascendancy

Worth pointing out that the ordering you get from a DFS is not the same as the topological ordering, in general. For example, if the graph has two paths ending in the same node (the branches "re-join"), DFS will visit that node via the first path, before the nodes in the second path. But you can use a DFS to construct the topological ordering. – Actinozoan

Answer 2

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.

Inordinate

Answer 3

Topological sort uses DFS in the following manner:

1. Call DFS
2. Note when all edges have been explored (i.e. the finishing times)
3. After a vertex is finished, insert an identifier at the head of the topological sort L
4. The completed list L is a topological sort

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.

Depolarize

what is yes ordering? – Expostulation

Answer 4

If you want to get a clear idea, you can try the following problem.

https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&category=0&problem=1246&mosmsg=Submission+received+with+ID+25820106

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

Millenarianism