Topological Sort

Given a graph G(V,E), find the topological sorted list of vertices.

First of , what is topological sorting?

From wikipedia, topological sort (sometimes abbreviated toposort) or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time.

For example, for the following graph one possible topological ordering is {7, 5, 3, 11, 8, 2, 9, 10}

The idea behind topological sort is to provide a partial ordering among the vertices of the graph such that if there is an edge from u to v then u≤v. So the final ordering would be v1≤v2≤v3<...≤vn. Note that, there can be node where there is no incoming edge only outgoing edges. These are called source. There are another type of vertices which has only incoming edges no outgoing edges. Such ages are called sink. So, we can say topological ordering starts with sources and ends with sink. We can actually traverse the graph in BFS from source to sink such a way that each time we traverse one hop we remove the sink and all edges we just traversed. As a result we may find more sinks and for each sink we do similar one level hop until we end up with no sink to start traverse with. This algorithm is called kahn’t topological sorting algorithm and described as follows –

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges (0-indegree i.e. sources)
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

Note that, topological sorting is not possible if there is a cycle in the graph. We can easily detect cycle by detecting a back edge i.e. an edge from a child to its ancestor in the BFS traversal.

DFS Based Algorithm – Tarjan’s Algorithm
Another way to traverse in topological order is to do DFS but instead of including current node in the result list during the DFS traversal, we want to hold it in a stack until all its neighbors has been traversed recursively. Below is the O(|V|+|E|) algorithm to find topologically sorted ordering of the vertices.

public static void topologicalSort(ArrayList<ArrayList<Integer>> adjList){
	int[] visited = new int[adjList.size()];
	Stack<Integer> stack = new Stack<Integer>();
	
	for(int i = 0; i<adjList.size(); i++){
		if(visited[i] == 0){
			topologicalSortDFS(i, adjList, visited, stack);
		}
	}
	
	System.out.print("topo sort: ");
	while(!stack.isEmpty()){
		System.out.print(stack.pop()+" ");
	}
	System.out.println();
}

public static void topologicalSortDFS(int u, ArrayList<ArrayList<Integer>> adjList, int[] visited, Stack<Integer> stack){
	//mark as visited
	visited[u] = 1;
	
	//first visit all the neighbors to ensure topo sort order
	for(int v : adjList.get(u)){
		if(visited[v] == 0){
			topologicalSortDFS(v, adjList, visited, stack);
		}
	}
	
	stack.add(u);
}

There are many applications of topological sorting including but not limited to –

1. Finding shortest path in a directed graph (weighted or unweighted)
2. Scheduling jobs/tasks from the given dependencies among jobs. 
3. Dependency Injection.