Problem statement: Given a graph, find the topological order for the given graph.
Topological sort: The linear ordering of nodes/vertices such that if there exists an edge between 2 nodes u,v then ‘u’ appears before ‘v’.
Example:
Example: Input:Output: 4 5 2 0 3 1 Explanation: 4 is appearing before its neighbours (1,0) 5 is appearing before its neighbours (0,2) 2 is appearing before its neighbours (3) 3 is appearing before its neighbours (1)
Output: 4 5 2 0 3 1
Explanation: 4 is appearing before its neighbours (1,0)
5 is appearing before its neighbours (0,2)
2 is appearing before its neighbours (3)
3 is appearing before its neighbours (1)
Note: This can be possible only for DAG ( Directed acyclic graph) because in an undirected graph we can’t decide which node will come first because there will be no direction, and if there is a cycle topological order will not be possible (See below figure to understand why it is not possible for graphs containing cycle).
2 ->3 ->4 ->2 here if you can observe
2 is appearing before 3
3 is appearing before 4
4 is appearing before 2
But 2 has already appeared before 4, So topological ordering will not be possible
Intuition:
The question states that if there is an edge between u and v then u should appear before v, Which means we have to start this question from a node that doesn’t have any previous edges. But how to find that node that has no edge before if? Here, we use the concept of in-degree (Number of edges pointing toward a node). We find an in-degree which has indegree=0 and we start from this. We use the Indegree concept to find topological sorting. Let’s see how.
Approach:
- In order to maintain the In-degree of each and every node, we take an array of size v( where v is the number of nodes).
- Find in-degree of all nodes and fill them in an array
- Now take Queue data structure and add nodes that have in-degree is 0 (as we discussed in the intuition), and simply apply bfs on queue with some condition.
- Take the top/peek node from Queue ( let the popped node be x), add this x to our answer. (If you can observe clearly the above step is nothing but Normal BFS traversal).
We’ll apply some conditions to the BFS:- Now take neighbour nodes of popped nodes and reduce their in-degree by 1.
- Check if any of the popped element nodes in degree becomes 0, after reducing in-degree by 1 if it happens then add this neighbour element to the queue for which the in-degree became zero.
- Repeat step 4 till the queue becomes empty.
We’ll apply some conditions to the BFS:
a) Now take neighbour nodes of popped nodes and reduce their indegree by 1.
b) Check if any of popped element nodes in degree become 0, after reducing in-degree by 1, if it happens then add this neighbour element which in-degree became 0 to the queue.
Let’s see how it works pictorially:
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> topo(int N, vector<int> adj[]) {
queue<int> q;
vector<int> indegree(N, 0);
for(int i = 0;i<N;i++) {
for(auto it: adj[i]) {
indegree[it]++;
}
}
for(int i = 0;i<N;i++) {
if(indegree[i] == 0) {
q.push(i);
}
}
vector<int> topo;
while(!q.empty()) {
int node = q.front();
q.pop();
topo.push_back(node);
for(auto it : adj[node]) {
indegree[it]--;
if(indegree[it] == 0) {
q.push(it);
}
}
}
return topo;
}
};
int main()
{
vector<int> adj[6];
adj[5].push_back(2);
adj[5].push_back(0);
adj[4].push_back(0);
adj[4].push_back(1);
adj[3].push_back(1);
adj[2].push_back(3);
Solution obj;
vector<int> v=obj.topo(6, adj);
for(auto it:v)
cout<<it<<" ";
return 0;
}Output:
4 5 2 0 3 1
Time Complexity: O(N+E)
Space complexity: O(N)+O(N)
Java Code
import java.util.*;
import java.io.*;
import java.lang.*;
class Solution
{
public boolean isCyclic(int N, ArrayList<ArrayList<Integer>> adj) {
int topo[] = new int[N];
int indegree[] = new int[N];
//finding indegree
for(int i = 0;i<N;i++) {
for(Integer it: adj.get(i)) {
indegree[it]++;
}
}
Queue<Integer> q = new LinkedList<Integer>();
for(int i = 0;i<N;i++) {
//adding nodes to queue with indegree = 0
if(indegree[i] == 0) {
q.add(i);
}
}
int cnt = 0;
int ind=0;
while(!q.isEmpty()) {
Integer node = q.poll();
topo[ind++] = node;
cnt++;
//getting neighbour nodes of popped node and decreasing their
indegree by1
for(Integer it: adj.get(node)) {
indegree[it]--;
if(indegree[it] == 0) {
q.add(it);
}
}
}
//printing topological ordering of nodes
for (int i=0;i< topo.length;i++){
System.out.print(topo[i]+" ");
}
if(cnt == N) return false;
return true;
}
}
public class TopoLogicalSortBFS {
public static void main(String args[]) {
ArrayList < ArrayList < Integer >> adj = new ArrayList < > ();
// adding new arraylists to 'adj' to add neighbour nodes
for (int i = 0; i < 6; i++) {
adj.add(new ArrayList < > ());
}
adj.get(5).add(2);
adj.get(5).add(0);
adj.get(4).add(0);
adj.get(4).add(1);
adj.get(3).add(1);
adj.get(2).add(3);
new Solution().isCyclic(6,adj);
}
}
Output:
4 5 2 0 3 1
Time Complexity: O(N+E)
Space complexity: O(N)+O(N)
Special thanks to Sai bargav Nellepalli for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article