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