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.
Like IDeserve?
Support us by whitelisting IDeserve in your ad-blocker.
Thanks, -Team IDeserve
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
Like IDeserve?
Support us by whitelisting IDeserve in your ad-blocker.