kahn 27s algorithm

Solutions on MaxInterview for kahn 27s algorithm by the best coders in the world

showing results for - "kahn 27s algorithm"
Léa
04 Mar 2017
1//Topological sort using BFS (Kahn's Algorithm)
2#include<bits/stdc++.h>
3using namespace std;
4void addedge(vector<int>adj[],int u,int v)
5{
6    adj[u].push_back(v);
7}
8void toposort(vector<int>adj[],int n)
9{
10    queue<int>q;
11    vector<int>indegree(n,0);
12    for(int i=0;i<n;i++)
13    {
14        for(auto it: adj[i])
15        {
16            indegree[it]++;
17        }
18    }
19    for(int i=0;i<n;i++)
20    {
21        if(indegree[i]==0)
22        {
23            q.push(i);
24        }
25    }vector<int>topo;
26    while(!q.empty())
27    {
28        int node=q.front();
29        q.pop();
30        topo.push_back(node);
31        for(auto it:adj[node])
32        {
33            indegree[it]--;
34            if(indegree[it]==0)
35            {
36                q.push(it);
37            }
38        }
39
40    }
41    int si=topo.size();
42    for(int i=0;i<si;i++)
43    {
44        cout<<topo[i]<<" ";
45    }
46}
47int main()
48{
49    int vertex,edges;
50    cout<<"Enter the number of vertex and edges:"<<endl;
51    cin>>vertex>>edges;
52    vector<int>adj[vertex];
53    int a,b;
54    cout<<"Enter the links:"<<endl;
55    for(int i=0;i<vertex;i++)
56    {
57        cin>>a>>b;
58        addedge(adj,a,b);
59    }
60   // for(int i=0;i<vertex;i++)
61    //{
62        toposort(adj,vertex);
63    //}
64
65    return 0;
66}
67