-
Notifications
You must be signed in to change notification settings - Fork 0
/
Topological_Sort_using_BFS.cpp
67 lines (67 loc) · 1.24 KB
/
Topological_Sort_using_BFS.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include<map>
#include<list>
#include<queue>
#include<cstring>
using namespace std;
class Graph{
list<int> *L;
int V;
public:
Graph(int V)
{
this->V=V;
L=new list<int>[V];
}
void AddEdge(int x,int y)
{
L[x].push_back(y);
}
void topological_sort()
{
int *indegree=new int[V];
for(int i=0; i<V; i++)
indegree[i]=0;
for(int i=0; i<V; i++)
{
for(auto Y : L[i])
{
indegree[Y]++;
}
}
queue<int> q;
for(int i=0; i<=V; i++)
{
if(indegree[i]==0)
{
q.push(i);
}
}
while(!q.empty())
{
int node=q.front();
cout<<node<<" ";
q.pop();
for(auto nbr:L[node])
{
indegree[nbr]--;
if(indegree[nbr]==0)
{
q.push(nbr);
}
}
}
}
};
int main()
{
Graph G(6);
G.AddEdge(0, 2);
G.AddEdge(1, 2);
G.AddEdge(1, 4);
G.AddEdge(2, 3);
G.AddEdge(2, 5);
G.AddEdge(3, 5);
G.AddEdge(4, 5);
G.topological_sort();
}