Learn-dsa..in 30 days!



























CC-11 : Implement Topological Sort Algorithm.

Description:

In topological sort of graph vertices, for each directed edge u->v, then u will come before v when the vertices are sorted topologically. Given an input graph, sort its elements using Topological Sort.

Test cases and expected outputs:

Input Parameters Expected outputs
vertex 0->1->2->3->4
vertex 1->2
vertex 2->3
vertex 3->4
vertex 4 		Topological Sort:
0, 1, 2, 3, 4,
vertex 0->1->2
vertex 1->2
vertex 2->3->4
vertex 3
vertex 4 		Topological Sort:
0, 1, 2, 4, 3,

Pseudocode:

Class SortTopologicalSortDfs:

Initialize an int variable named visited to store information whether a particular vertice in the graph has been visited.
Initialize a String variable named dfsTraversal to hold output of DFS traversal of the graph.
Integer member vertices stores the number of vertices in the graph.
The edges of graph should be added to ArrayList called adjacencyLists (refer to graphs chapter to construct Adjacency lists of graph edges).

topologicalSort():

Initialize variable named stack of type Stack.
Iterate through vertices of graph using for loop with idx as iteration variable and values of idx ranging from 0 to vertices where idx is incremented by 1 after each iteration:
Call dfs(idx, stack).
Initialize integer array variable sorted to hold the sorted vertices elements.
Initialize integer variable idx to 0.
While stack.size !=0 execute the following steps:
Set Sorted[idx]=stack.remove().
Increment idx by one.
The element of nums array have been sorted now using Topological Sort into array named sorted, so return sorted array from the method.

dfsTraversal(vertex, stack):

Set visited[vertex] to 1.
Extract vertices connected to vertex from the adjacencyList.
Iterate through vertices connected to current vertex using iterator:
Set variable adjacentNode to point to current connected vertice in the iterator.
If visited[adjacentNode] is not 1, then:
Call dfs(adjacentNode) recursively.
• Add vertex to stack.

Code:

public class SortTopologicalSortDfs {

 private int vertices;
 private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
 private int[] visited;
 String dfsTraversal=new String();
 
 public SortTopologicalSortDfs(int vertices) {
	 this.vertices=vertices;
	 visited=new int[vertices];
	 for (int iIdx=0; iIdx < vertices; iIdx++) {
		 adjacencyLists.add(new ArrayList<Integer>());
		 visited[iIdx]=0;
	 }
 }
 
 public void addEdge(int source, int dest) {
	 adjacencyLists.get(source).add(dest);
	 //adjacencyLists.get(dest).add(source);
 }
 
 public int[] topologicalSort() {
	  Stack stack=new Stack();
	  for (int idx=0; idx < vertices; idx++) {
		  if (visited[idx]==0) {
			  dfs(idx,stack);
		  }
	  }
	  int[]sorted=new int[vertices];
	  int idx=0;
	  while (stack.getSize()!=0) {
		  sorted[idx]=stack.remove();
		  idx++;
	  }	
	  return sorted;
 }
 
 public void dfs(int vertex, Stack stack) {
	 visited[vertex]=1;
	 Iterator<Integer> itr=adjacencyLists.get(vertex).iterator();
	 while (itr.hasNext()) {
		 int adjacentNode=itr.next();
		 if (visited[adjacentNode]==0) {
			 dfs(adjacentNode,stack);
		 }
	 }
	 stack.add(vertex);
 }
 }

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us