Topological Sorting

Problems List

Course Schedule II

DFS based approach

TBD

https://www.geeksforgeeks.org/topological-sorting/

``````// A Java program to print topological sorting of a DAG
import java.io.*;
import java.util.*;

// This class represents a directed graph using adjacency
// list representation
class Graph
{
private int V; // No. of vertices

//Constructor
Graph(int v)
{
V = v;
for (int i=0; i<v; ++i)
}

// Function to add an edge into the graph

// A recursive function used by topologicalSort
void topologicalSortUtil(int v, boolean visited[],
Stack stack)
{
// Mark the current node as visited.
visited[v] = true;
Integer i;

// Recur for all the vertices adjacent to this
// vertex
while (it.hasNext())
{
i = it.next();
if (!visited[i])
topologicalSortUtil(i, visited, stack);
}

// Push current vertex to stack which stores result
stack.push(new Integer(v));
}

// The function to do Topological Sort. It uses
// recursive topologicalSortUtil()
void topologicalSort()
{
Stack stack = new Stack();

// Mark all the vertices as not visited
boolean visited[] = new boolean[V];
for (int i = 0; i < V; i++)
visited[i] = false;

// Call the recursive helper function to store
// Topological Sort starting from all vertices
// one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, stack);

// Print contents of stack
while (stack.empty()==false)
System.out.print(stack.pop() + " ");
}

// Driver method
public static void main(String args[])
{
// Create a graph given in the above diagram
Graph g = new Graph(6);

System.out.println("Following is a Topological " +
"sort of the given graph");
g.topologicalSort();
}
}
// This code is contributed by Aakash Hasija
``````

BFS based approach

Kahn’s algorithm for Topological Sorting (In-degree Based)

Source: GeeksforGeeks: https://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/

Definition

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

The approach is based on:

A DAG has at least one vertex with in-degree 0 and one vertex with out-degree 0.

Algorithm

Steps involved in finding the topological ordering of a DAG:

Step-1: Compute in-degree (number of incoming edges) for each of the vertex present in the DAG and initialize the count of visited nodes as 0.

Step-2: Pick all the vertices with in-degree as 0 and add them into a queue (Enqueue operation)

Step-3: Remove a vertex from the queue (Dequeue operation) and then.

1. Increment count of visited nodes by 1.
2. Decrease in-degree by 1 for all its neighboring nodes.
3. If in-degree of a neighboring nodes is reduced to zero, then add it to the queue.

Step 5: Repeat Step 3 until the queue is empty.

Step 5 :If count of visited nodes is not equal to the number of nodes in the graph then the topological sort is not possible for the given graph.

How to find in-degree of each node?
There are 2 ways to calculate in-degree of every vertex:
Take an in-degree array which will keep track of
1)Traverse the array of edges and simply increase the counter of the destination node by 1.

``````for each node in Nodes
indegree[node] = 0;
for each edge(src,dest) in Edges
indegree[dest]++
``````

Time Complexity: O(V+E)

2)Traverse the list for every node and then increment the in-degree of all the nodes connected to it by 1.

``````    for each node in Nodes
If (list[node].size()!=0) then
for each dest in list
indegree[dest]++;
``````

Time Complexity: The outer for loop will be executed V number of times and the inner for loop will be executed E number of times, Thus overall time complexity is O(V+E).

The overall time complexity of the algorithm is O(V+E)

Implementation

``````// A Java program to print topological sorting of a graph
// using indegrees
import java.util.*;

//Class to represent a graph
class Graph
{
int V;// No. of vertices

//An Array of List which contains
//references to the Adjacency List of
//each vertex
public Graph(int V)// Constructor
{
this.V = V;
for(int i = 0; i < V; i++)
}

// function to add an edge to graph
{
}
// prints a Topological Sort of the complete graph
public void topologicalSort()
{
// Create a array to store indegrees of all
// vertices. Initialize all indegrees as 0.
int indegree[] = new int[V];

// Traverse adjacency lists to fill indegrees of
// vertices. This step takes O(V+E) time
for(int i = 0; i < V; i++)
{
for(int node : temp)
{
indegree[node]++;
}
}

// Create a queue and enqueue all vertices with
// indegree 0
for(int i = 0;i < V; i++)
{
if(indegree[i]==0)
}

// Initialize count of visited vertices
int cnt = 0;

// Create a vector to store result (A topological
// ordering of the vertices)
Vector <Integer> topOrder=new Vector<Integer>();
while(!q.isEmpty())
{
// Extract front of queue (or perform dequeue)
// and add it to topological order
int u=q.poll();

// Iterate through all its neighbouring nodes
// of dequeued node u and decrease their in-degree
// by 1
{
// If in-degree becomes zero, add it to queue
if(--indegree[node] == 0)
}
cnt++;
}

// Check if there was a cycle
if(cnt != V)
{
System.out.println("There exists a cycle in the graph");
return ;
}

// Print topological order
for(int i : topOrder)
{
System.out.print(i+" ");
}
}
}
// Driver program to test above functions
class Main
{
public static void main(String args[])
{
// Create a graph given in the above diagram
Graph g=new Graph(6);