Topological Sorting of a Directed Acyclic Graph.

Topological sorting for Directed Acyclic Graph is a linear ordering of vertices such that for every directed edge uv, vertex 'u' comes before 'v' in the ordering.  
For a given directed acyclic graph, print the vertices in topologically sorted order.  
For example in this simple graph(3->1->4), there is a directed edge from vertex 3 to vertex 1 and from vertex 1 to vertex 4. Topologically sorted order of vertices would be 3,1,4.


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Algorithm/Insights

The idea is to use the breadth-first traversal combined with hash table to count the in-degrees of vertices.
1. Count in-degree of all vertices.
2. Pick any vertex 'v' which has in-degree of 0.
3. Print 'v'. Remove the vertex 'v' and all edges coming out of it. In other words, decrement in-degrees of all neighbors of vertex 'v' by 1.
4. Repeat steps 2 and 3 till all vertices are removed.

Please check out the video for an illustrative explanation.


Algorithm Visualization




Code Snippet

			
package com.ideserve.nilesh.questions;

import java.util.ArrayList;
import java.util.Hashtable;

public class  Graph
{
	static private class GraphNode
	{
		int nodeId;
		GraphNode next;
		
		public GraphNode(int id)
		{
			this.nodeId = id;
		}
	}
	
	ArrayList<GraphNode> nodeList;
	
	public Graph()
	{
		nodeList = new ArrayList<GraphNode>();
	}
	
	public GraphNode addNode(int id)
	{
		GraphNode node = new GraphNode(id);
		nodeList.add(0, node);

		return nodeList.get(0); 
	}
	
	// adding edge from id1 to id2
	// if either of these does not exist then create and add
	public void addEdge(int id1, int id2)
	{
		// search for id1 and id2
		boolean node1Found = false, node2Found = false;
		GraphNode node1  = null, node2 = null;
		
		for (int i = 0; i < nodeList.size(); i++)
		{
			if (nodeList.get(i).nodeId == id1)
			{
				node1Found = true;
				node1 = nodeList.get(i);
			}
			if (nodeList.get(i).nodeId == id2)
			{
				node2Found = true;
				node2 = nodeList.get(i);
			}
			if (node1Found && node2Found) break;
		}
		
		
		if (!node1Found)
		{
			node1 = this.addNode(id1); 
		}
		
		if (!node2Found)
		{
			node2 = this.addNode(id2); 
		}
		
		GraphNode temp = new GraphNode(id2);
		temp.next = node1.next;
		node1.next = temp;
		
		return;
	}
	
	
	public GraphNode getNode(int id)
	{
		for (int i = 0; i < nodeList.size(); i++)
		{
			if (id == nodeList.get(i).nodeId)
			{
				return nodeList.get(i);
			}
			
		}
		
		return null;
	}
	

	public void printTopoSortedNodes()
	{
		Hashtable inDegrees = new Hashtable <Integer, Integer>();
		ArrayList<GraphNode> zeroDegreeList  = new ArrayList<GraphNode>();
		ArrayList<GraphNode> nodes = this.nodeList;
		
		// this for loop counts the in-degrees for all nodes.
		// adds nodes having in-degree > 0 to in-Degrees hashtable 
		for (int i = 0; i < nodes.size(); i++)
		{
			GraphNode temp = nodes.get(i);
			temp  = temp.next;
			while (temp != null)
			{
				int count = (inDegrees.get(temp.nodeId) == null) ? 0 : (int)inDegrees.get(temp.nodeId);
				inDegrees.put(temp.nodeId, count+1);
				temp = temp.next;
			}
		}
	
		// nodes which are not added to in-degree hashtable have in-degree = 0
		// create zeroDegree list of such nodes
		for (int i = 0; i < nodes.size(); i++)
		{
			GraphNode temp = nodes.get(i);
			
			// nodes with zero indegree would not be in the hashtable 
			// since they are not in anyone's neighbor list
			if (inDegrees.get(temp.nodeId) == null)
			{
				zeroDegreeList.add(0, temp);
			}
			
		}
		
		// take out a node from zeroDegree list
		// print that node, remove all out-edges associated with it and update zeroDegree list.
		while (!zeroDegreeList.isEmpty())
		{
			GraphNode curr = zeroDegreeList.remove(0);
			
			// print topo sort: output! 
			System.out.println(curr.nodeId);
			
			GraphNode temp = curr.next;
			
			// update the in-degree for all the neighbors of the current vertex
			while (temp != null)
			{
				int prevInDegree = (int) inDegrees.get(temp.nodeId);
				
				inDegrees.put(temp.nodeId, prevInDegree-1);
				if (prevInDegree == 1)
				{
					zeroDegreeList.add(this.getNode(temp.nodeId));
				}
				temp = temp.next;
			}
		}
		
	}
	
	public static void main(String[] args) {
		
		// create a graph here
		Graph gr = new Graph();
		
		gr.addEdge(1,2);
		gr.addEdge(1,6);
	
		gr.addEdge(3,4);
		gr.addEdge(3,1);
		
		gr.addEdge(4,5);
		
		gr.addEdge(6,2);
		gr.addEdge(6,4);
		gr.addEdge(6,5);
			
		// print the vertices in topologically sorted order
		gr.printTopoSortedNodes();
	}
}
		

Order of the Algorithm

Time Complexity is O(|E| + |V|)
Space Complexity is O(|V|)


Contribution

  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.


    Nilesh More