Dear reader, welcome to the article on the problem named 'Order of Compilation'. This algorithm is popularly known as 'Topological Sorting' of directed acyclic graphs. There are broadly two methods of solving topological sort:
- Using Depth First Search (DFS)
- Using Breadth First Search (BFS) - Also known as Kahn's Algorithm
In this article, we will be only discussing the DFS based approach.
- You are given a directed acyclic graph. The vertices represent tasks and edges represent dependencies between tasks.
- You are required to find and print the order in which tasks could be done. The task that should be done at last should be printed first and the task which should be done first should be printed last.
- This kind of ordering can be achieved by the topological sort of the graph.
- Topological sort: A permutation of vertices for a directed acyclic graph is called topological sort if for all directed edges uv, u appears before v in the graph.
Topological sorting for a graph is not possible if the graph is undirected or if the graph has a cycle. Hence, it must be Directed Acyclic only.
Note: Input is given in the form of adjacency list.
Output: [4, 5, 6, 0, 1, 2, 3]
For a given graph, there can be many topological ordering of the vertices possible.
WHAT: Let us first see WHAT we will have to do to find topological ordering.We will perform a DFS traversal from each unvisited vertex, and add the nodes into a stack data structure in the postorder (while returning from the recursive call). All the vertices will be pushed into the stack in one of the valid topological ordering.
By adding a given element x to the stack in postorder, we are ensuring that all the vertices which is x dependent upon, must be already present in the stack, as we have traversed all of the unvisited neighbours of x, and are now returning.
We can start the DFS traversal from any vertex, but we must do DFS traversal from each unvisited vertex. Hence, no vertex should be absent in the topological ordering.
HOW: Now, let us see how we can store the topological ordering by filling the stack in the postorder of recursion calls.