ikReza

BFS basic traversal

Feb 12th, 2020
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.36 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. #define MAX 10000
  8.  
  9. vector <int> edgesIn[MAX], edgesOut[MAX];
  10.  
  11. int level[10];
  12. bool visited[10];
  13.  
  14. void bfs(int s)
  15. {
  16.     queue <int> q;
  17.     q.push(s);
  18.     level[s] = 0;
  19.     visited[s] = true;
  20.  
  21.     while(!q.empty())
  22.     {
  23.         int p = q.front();
  24.         cout << p << " ";
  25.         q.pop();
  26.         for(int i = 0; i < edgesOut[p].size(); i++)
  27.         {
  28.             if(visited[edgesOut[p][i]] == false)
  29.             {
  30.                 level[edgesOut[p][i]] = level[p] + 1;
  31.                 q.push(edgesOut[p][i]);
  32.                 visited[edgesOut[p][i]] = true;
  33.             }
  34.         }
  35.     }
  36. }
  37.  
  38. int main()
  39. {
  40.     int nodeNo, edgeNo;
  41.     cin >> nodeNo >> edgeNo;
  42.  
  43.     for(int i = 0; i < edgeNo; i++)
  44.     {
  45.         int x, y;
  46.         cin >> x >> y;
  47.         edgesOut[x].push_back(y);
  48.         //edgesOut[y].push_back(x);      //undirected
  49.        // edgesIn[y].push_back(x);
  50.     }
  51.  
  52.    /* for(int i = 0; i < nodeNo; i++) //counting indegree and outdegree
  53.     {
  54.         cout << "Indegree of node " << i << " : " << edgesIn[i].size() << endl;
  55.         cout << "Outdegree of node " << i << " : " << edgesOut[i].size() << endl;
  56.     }*/
  57.  
  58.     bfs(2); //source or starting node
  59.  
  60.     return 0;
  61. }
  62. /* Sample input
  63. 4 6
  64. 0 1
  65. 0 2
  66. 1 2
  67. 2 0
  68. 2 3
  69. 3 3
  70. Sample output: 2 0 3 1 */
Advertisement
Add Comment
Please, Sign In to add comment