Find any Topological Sorting of the given Graph

Level - Medium

Statement

Given a Graph G with V vertices and E edges, Find any Topological Order of given Graph. In input we have provided number of Vertex and Adjacency list of a Graph.

Example 1

Input:

adjacency_list = [[], [3], [3], [], [0,1], [0,2]]

0: []
1: [3]
2: [3]
3: []
4: [0,1]
5: [0,2]

Output:

output = [5, 4, 2, 1, 3, 0]

Input:

adjacency_list = [[1], [2], [3], [0]]
0: [1]
1: [2]
2: [3]
3: [0]

Output:

output = [] // as graph has cycle so topological_order is not possible

You can try this at:

• https://practice.geeksforgeeks.org/problems/topological-sort/1

Algorithm Steps

1. Initialize a vector topological_order of size V to store the topological order.
2. Calculate the in-degree for each vertex in the graph.
3. Initialize a queue q to store vertices with an in-degree of 0.
4. Iterate over each vertex and check if its in-degree is 0. If so, enqueue it in q.
5. Initialize an index variable to keep track of the current position in topological_order.
6. While the queue q is not empty, perform the following steps:
   • Dequeue the front element from q.
   • Add the dequeued vertex to topological_order at the current index position.
   • Iterate over the neighbors of the dequeued vertex and decrease their in-degree by 1.
   • If the in-degree of a neighbor becomes 0, enqueue it in q.
   • Increment the index variable.
7. Return the topological_order vector, representing the topological ordering of the graph.

Kahn's Algorithm Dry Run(Visual Walkthrough)

Implementation

Java

class Solution
{

    static int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj) 
    {
        int[] topological_order = new int[V];
        // calculate inorder for given graph
        int[] indegree = new int[V];
        for(int i=0;i<V;i++){
            ArrayList<Integer> neighbours = adj.get(i);
            for(Integer neighbour: neighbours)indegree[neighbour]++;
        }
        // add all the node with 0 indegree in queue
        Queue<Integer> q = new LinkedList<>();
        for(int i=0;i<V;i++){
            if(indegree[i]==0)q.add(i);
        }
        int index=0;
        while(!q.isEmpty()){
            int front = q.poll();
            topological_order[index++] = front;// add to result
            ArrayList<Integer> neighbours = adj.get(front);
            // decrease the indegree of all the neighbours and add in the queue if there indegree becomes 0
            for(Integer neighbour: neighbours){
                indegree[neighbour]--;
                if(indegree[neighbour]==0)q.add(neighbour);
            }
        }
        return topological_order;
    }
}

CPP

class Solution
{
	public:
	vector<int> topoSort(int V, vector<int> adj[]) 
	{
	     vector<int> topological_order(V, 0);
        // calculate inorder for given graph
        vector<int> indegree(V, 0);
        for (int i = 0; i < V; i++) {
            vector<int>& neighbours = adj[i];
            for (int neighbour : neighbours)
                indegree[neighbour]++;
        }
        // add all the nodes with 0 indegree to the queue
        queue<int> q;
        for (int i = 0; i < V; i++) {
            if (indegree[i] == 0)
                q.push(i);
        }
        int index = 0;
        while (!q.empty()) {
            int front = q.front();
            q.pop();
            topological_order[index++] = front; // add to result
            vector<int>& neighbours = adj[front];
            // decrease the indegree of all the neighbours and add to the queue if their indegree becomes 0
            for (int neighbour : neighbours) {
                indegree[neighbour]--;
                if (indegree[neighbour] == 0)
                    q.push(neighbour);
            }
        }
        return topological_order;
	}
};

Python

from collections import deque

class Solution:
    def topoSort(self,V, adj):
        topological_order = [0] * V
        # calculate inorder for given graph
        indegree = [0] * V
        for i in range(V):
            neighbours = adj[i]
            for neighbour in neighbours:
                indegree[neighbour] += 1
        # add all the nodes with 0 indegree to the queue
        q = deque()
        for i in range(V):
            if indegree[i] == 0:
                q.append(i)
        index = 0
        while q:
            front = q.popleft()
            topological_order[index] = front # add to result
            index += 1
            neighbours = adj[front]
            # decrease the indegree of all the neighbours and add to the queue if their indegree becomes 0
            for neighbour in neighbours:
                indegree[neighbour] -= 1
                if indegree[neighbour] == 0:
                    q.append(neighbour)
        return topological_order

Complexity

Time Complexity:

O(V+E)

Space Complexity:

O(V)

note

V denotes number of Vertex/Nodes and E denotes number of Edges in a Graph.