**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 1Explanation: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 toplease check out this articleSai bargav Nellepallifor contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam,