spider68

Topology sort Kahn's algorithm

May 24th, 2020
233
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.02 KB | None | 0 0
  1. void Graph::topologicalSort()
  2. {
  3.     vector<int> in_degree(V, 0);
  4.  
  5.     for (int u=0; u<V; u++)
  6.     {
  7.         list<int>::iterator itr;
  8.         for (itr = adj[u].begin(); itr != adj[u].end(); itr++)
  9.              in_degree[*itr]++;
  10.     }
  11.  
  12.     queue<int> q;
  13.     for (int i = 0; i < V; i++)
  14.         if (in_degree[i] == 0)
  15.             q.push(i);
  16.  
  17.     int cnt = 0;
  18.  
  19.     vector <int> top_order;
  20.  
  21.     while (!q.empty())
  22.     {
  23.         int u = q.front();
  24.         q.pop();
  25.         top_order.push_back(u);
  26.  
  27.         list<int>::iterator itr;
  28.         for (itr = adj[u].begin(); itr != adj[u].end(); itr++)
  29.             if (--in_degree[*itr] == 0)
  30.                 q.push(*itr);
  31.         cnt++;
  32.     }
  33.  
  34.     // Check if there was a cycle
  35.     if (cnt != V)
  36.     {
  37.         cout << "There exists a cycle in the graph\n";
  38.         return;
  39.     }
  40.  
  41.     // Print topological order
  42.     for (int i=0; i<top_order.size(); i++)
  43.         cout << top_order[i] << " ";
  44.     cout << endl;
  45. }
Add Comment
Please, Sign In to add comment