Prerequisites: Graphs, DFS
Problem: Check if for the given directed graph, topological ordering can be found or not.
Solution Approach: The solution utilizes DFS to perform two main tasks:
- Check if the given graph is a Directed Acyclic Graph (DAG).
- If it is a DAG, find and print a topological ordering of the vertices.
We’ve already discussed how to perform task 1 in previous sections, lets focus and reiterate the core idea behind task 2:
When starting from some vertex v , DFS tries to traverse along all edges outgoing from
v. It stops at the edges for which the ends have been already been visited previously, and traverses along the rest of the edges and continues recursively at their ends.
Thus, by the time of the function call \text{dfs}(v) has finished, all vertices that are reachable from v have been either directly (via one edge) or indirectly visited by the search.
Let’s append the vertex v to a list, when we finish \text{dfs}(v) . Since all reachable vertices have already been visited, they will already be in the list when we append v . Let’s do this for every vertex in the graph, with one or multiple depth first search runs. For every directed edge v \rightarrow u in the graph, u will appear earlier in this list than v , because u is reachable from v . So if we just label the vertices in this list with n-1, n-2, \dots, 1, 0 , we have found a topological order of the graph. In other words, the list represents the reversed topological order. So just reverse the topological order list if you need it else just checking the acyclicity is enough to tell whether topological ordering is possible or not.
Time complexity: O(N + M) as we are using DFS.
Space complexity: O(N) as we need to use additional space in DFS.