fork download
copy 
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. struct node
  5. {
  6.     int x;
  7.     node*link;
  8. };
  9.  
  10. node*r = NULL;
  11. node*f = NULL;
  12.  
  13. void enq(int y)
  14.  
  15. {
  16.  
  17.     node* obj = new node;
  18.  
  19.     obj->x = y;
  20.  
  21.     obj->link = NULL;
  22.  
  23.     if (r == NULL && f == NULL)
  24.     {
  25.         f = r = obj;
  26.         return;
  27.     }
  28.  
  29.     else
  30.     {
  31.         r->link = obj;
  32.         r = obj;
  33.  
  34.     }
  35. }
  36.  
  37. int isempty()
  38. {
  39.     return (f == NULL);
  40. }
  41.  
  42. int deq()
  43. {
  44.     int data;
  45.  
  46.     if (isempty())
  47.     {
  48.         cout << "Queue is empty\n";
  49.         return 0;
  50.     }
  51.  
  52.     else
  53.     {
  54.         data = f->x;
  55.         f = f->link;
  56.         if(f==NULL)
  57.               r=NULL;           // 'r' wasnt being reinitialized to NULL!!!
  58.         return data;
  59.     }
  60.  
  61. }
  62.  
  63.  
  64. int mat[30][30] = { 0 }, visit[30] = { 0 }, q[30];
  65.  
  66. void bfs(int k,int v)
  67.  
  68. {
  69.     int i, u;
  70.  
  71.       enq(k);
  72.  
  73.     while (!isempty())
  74.  
  75. {
  76.         u = deq();
  77.  
  78. cout << u+1 << endl;
  79.  
  80.         visit[u] = 1;
  81.  
  82.         for (i = 0; i < v; i++)
  83.  
  84.         {
  85.  
  86.             if (!visit[i] && mat[u][i])     // "[u][i]" instead of [k][i]
  87.             {
  88.                 //cout<<"++++"<<i+1<<endl;
  89.                 enq(i);
  90.             }
  91.  
  92.         }
  93.  
  94.     }
  95.  
  96. }
  97.  
  98. void bfst(int v)
  99.  
  100. {
  101. 	/*for(int i=0;i<v;i++,cout<<endl)
  102. 		for(int j=0;j<v;j++)
  103. 			cout<<mat[i][j]<<"\t";*/
  104.     int i;
  105.  
  106.     for (i = 0; i < v; i++)
  107.  
  108.     {
  109.  
  110.         if (!visit[i])
  111.  
  112.             bfs(i, v);
  113.  
  114.  
  115.     }
  116.  
  117. }
  118. int main()
  119. {
  120.     int i, j, k, v, e, l, m;
  121.  
  122. cout << "Enter the number of vertices and edges\n";
  123.  
  124.     cin >> v >> e;
  125.  
  126.  
  127.  
  128.     cout << "Enter the adjacenecy matrix\n";
  129.  
  130.     for (i = 0; i < e; i++)
  131.     {
  132.         cin >> l >> m;
  133.         mat[l - 1][m - 1] = 1;
  134.         mat[m - 1][l - 1] = 1;
  135.     }
  136.     bfst(v);
  137.  
  138.     return 0;
  139. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
6 3
1 2
2 6
4 5
stdout
copy 
Enter the number of vertices and edges
Enter the adjacenecy matrix
1
2
6
3
4
5
https://ideone.com/cPFhyU
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!