fork download
copy 
  1. /**
  2.  * Breadth First Search Traversal
  3.  */
  4. #include <iostream>
  5. #include <cstring>
  6.  
  7. using namespace std;
  8.  
  9. struct Node {
  10.  
  11.   int data;
  12.   struct Node *next;
  13. };
  14.  
  15. int nodes;
  16.  
  17. struct Node *List[ 100 ];//declare an array of pointers to struct Node
  18.  
  19. int matrix[100][100];
  20.  
  21. int Queue[ 100 ],//the queue
  22.  
  23.     first_index,
  24.  
  25.     last_index,
  26.  
  27.     used[ 100 ];
  28.  
  29. void ReadGraph() {
  30.  
  31.      int i, j;
  32.  
  33.      //freopen("graph.in","r",stdin);
  34.  
  35.      cin>>nodes;
  36.  
  37.      while(cin>>i>>j) {
  38.  
  39.        struct Node *c = new Node;
  40.        c->data = j;
  41.        c->next = List[i];
  42.        List[i] = c;
  43.      }
  44. }
  45.  
  46. void AdjancencyMatrix() {
  47.  
  48.      int i, j;
  49.  
  50.      freopen("graph.in","r",stdin);
  51.  
  52.      cin>>nodes;
  53.  
  54.      while(cin>>i>>j) {
  55.  
  56.            matrix[i][j] = 1;
  57.      }
  58. }
  59.  
  60. void DisplayGraph() {
  61.  
  62.   printf("%s\n","List Adjancency List");
  63.   for(int i = 1; i <= nodes; ++i) {
  64.  
  65.       struct Node *p = List[i];
  66.       printf("Node %d: ", i);
  67.  
  68.       while(p) {
  69.         std::cout<<p->data<<" ";
  70.         p = p->next;
  71.       }
  72.       printf("\n");
  73.   }
  74. }
  75.  
  76. void bfs( int node ) {
  77.  
  78.      memset(used, 0, sizeof(used));
  79.  
  80.      first_index = last_index = 1;
  81.      Queue[first_index] = node;
  82.  
  83.      while(first_index<=last_index) {
  84.        struct Node *c = List[Queue[first_index]];
  85.        while(c) {
  86.          if(used[c->data] == 0) {
  87.             last_index++;
  88.             Queue[last_index] = c->data;
  89.             used[c->data] = 1;
  90.          }
  91.          c = c->next;
  92.        }
  93.        first_index++;
  94.      }
  95.  
  96.      printf("Breadth First Search: \n");
  97.  
  98.      for(int i = 1; i <= nodes; ++i) {
  99.  
  100.        printf("%d ", Queue[i]);
  101.      }
  102. }
  103.  
  104.  
  105. void bfs_AdjMat( int node ) {
  106.  
  107.      memset( used, 0, sizeof( used ) );
  108.  
  109.      first_index = last_index = 1;
  110.  
  111.      Queue[ first_index ] = node;
  112.  
  113.      while( first_index <= last_index ) {
  114.  
  115.             for(int i = 1; i <= nodes; ++i) {
  116.  
  117.                 if(matrix[ Queue[ first_index ] ][ i ] == 1 && used[i] == 0) {
  118.  
  119.                      used[i] = 1;
  120.                      last_index++;
  121.                      Queue[last_index] = i;
  122.                 }
  123.             }
  124.  
  125.             first_index++;
  126.      }
  127.  
  128.      printf("Breadth First Search: \n");
  129.      for(int i = 1; i <= nodes; ++i) {
  130.  
  131.          printf("%d ", Queue[i]);
  132.      }
  133.      printf("\n");
  134. }
  135.  
  136. int main(int argc, char const *argv[]) {
  137.   ReadGraph();
  138.   DisplayGraph();
  139.   bfs(1);
  140.   //AdjancencyMatrix();
  141.   //bfs_AdjMat(1);
  142.   return 0;
  143. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
7
1 2
1 3
1 6
2 4
2 5
3 6
3 7
stdout
copy 
List Adjancency List
Node 1: 6 3 2 
Node 2: 5 4 
Node 3: 7 6 
Node 4: 
Node 5: 
Node 6: 
Node 7: 
Breadth First Search: 
1 6 3 2 7 5 4
https://ideone.com/NVEuN0
BFS
language:
C++ (gcc 8.3)
created:
318 days 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!