fork download
copy 
  1. #include <stdio.h>
  2. #include <memory.h>
  3. #define FIN "graph.in"
  4. #define FOUT "bfs.out"
  5. #define DIM 30
  6.  
  7. //Breadth First Search
  8. void bfs(int mat[][DIM], int n, int startNode) {
  9.  
  10.      int explored[DIM],
  11.          Q[DIM],
  12.          first, last,
  13.          node;
  14.  
  15.      memset(explored, 0, sizeof(explored));
  16.  
  17.      Q[0] = startNode;
  18.  
  19.      first = last = 0;
  20.  
  21.      explored[startNode] = 1;
  22.  
  23.      while( first <= last ) {
  24.  
  25.        node = Q[first];
  26.  
  27.        for(int j = 0; j < n; ++j) {
  28.  
  29.           //is adjcency and not explored  execute
  30.            if(explored[ j ]==0 && mat[ node ][ j ]==1) {
  31.  
  32.              Q[ ++last ] = j;
  33.  
  34.              explored[ j ] = 1;
  35.            }
  36.        }
  37.  
  38.        first++;
  39.      }
  40.  
  41.      printf("Breadh First Search:\n");
  42.  
  43.      for(int j = 0; j < n;++j) {
  44.  
  45.        printf("%d ", Q[j]+1);
  46.  
  47.      }
  48.  
  49.      printf("\n");
  50. }
  51.  
  52. int main(int argc, char const *argv[]) {
  53.  
  54.   int matrix[DIM][DIM], nodes, i, j;
  55.  
  56.   //freopen(FIN, "r", stdin);
  57.   int startNode;
  58.   //freopen(FOUT, "w", stdout);
  59.   scanf("%d", &nodes);
  60.  
  61.   for(i = 0; i < nodes; ++i) {
  62.     for(j = 0; j < nodes; ++j) {
  63.       scanf("%d", &matrix[i][j]);
  64.     }
  65.   }
  66.  
  67.   //Display matrix adjcency
  68.   /*
  69.   for(i = 0; i < nodes; ++i) {
  70.     for(j = 0; j < nodes; ++j) {
  71.       printf("%d ", matrix[i][j]);
  72.     }
  73.     printf("\n");
  74.   }
  75.   */
  76.   startNode = 2;
  77.  
  78.   bfs( matrix, nodes, startNode );
  79.  
  80.   return 0;
  81. }
Success #stdin #stdout 0s 5464KB
comments (?)
stdin
copy 
8
0 1 1 0 0 0 0 0
1 0 1 1 0 0 0 0
1 1 0 1 1 1 0 1
0 1 1 0 1 0 1 0
0 0 1 1 0 1 1 0
0 0 1 0 1 0 1 1
0 0 0 0 1 1 0 1
0 0 1 0 0 1 1 0
stdout
copy 
Breadh First Search:
3 1 2 4 5 6 8 7
https://ideone.com/B4TMtl
Breadth First Search Iteration
language:
C (gcc 8.3)
created:
1 year 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!