fork download 
  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include <memory.h>
  4. #define FIN "bfs.in"
  5. #define FOUT "bfs.out"
  6. #define SIZE 100100
  7.  
  8. struct TNode {
  9. 	   int data;
  10. 	   struct TNode *next;
  11. };
  12.  
  13. typedef struct TNode Node;
  14.  
  15.  
  16. void addEdge(Node** list, int x, int y) {
  17.  
  18. 	Node *c = (Node*)malloc(sizeof(Node));
  19.  
  20. 	      c->data = y; 
  21. 	      c->next = list[x];
  22. 	      list[x] = c; 
  23. }
  24.  
  25. void bfs(Node **list, int nodes, int start) {
  26.  
  27.         int queue[ SIZE ],
  28.  
  29.             visited[ SIZE ],
  30.  
  31.             first = 0,
  32.  
  33.             last = 0;
  34.  
  35.         memset(visited, 0, sizeof(visited));
  36.  
  37.         visited[ start ] = 1;
  38.  
  39.         queue[ first ] = start;
  40.  
  41.         while( first <= last ) {
  42.  
  43.               int node = queue[ first ];
  44.  
  45.               Node*curr = list[node];
  46.  
  47.               while(curr) {
  48.  
  49.                 if(visited[curr->data] == 0) {
  50.  
  51.                    queue[++last] = curr->data;
  52.  
  53.                    visited[curr->data] = 1;
  54.  
  55.                 }     
  56.                 curr = curr->next;
  57.               }
  58.  
  59.               first++;                     
  60.  
  61.         }
  62.  
  63.         //freopen(FOUT, "w", stdout);
  64.  
  65.         for(int i = 0; i < nodes; ++i) printf("%d ", queue[i]);
  66. }
  67.  
  68. int main(int argc, char const *argv[])
  69. {
  70. 	Node *list[SIZE];
  71.  
  72.   	int nodes, edges, i, j; 
  73.  
  74.     //freopen(FIN, "r", stdin);
  75.  
  76.     scanf("%d %d" , &nodes, &edges); 
  77.  
  78.     while(edges--) {
  79.  
  80.           scanf("%d %d" , &i, &j);
  81.  
  82.           addEdge(list, i,j);
  83.     }
  84.  
  85.     bfs(list, nodes, 4);
  86. 	return 0;
  87. }
Success #stdin #stdout 0s 4456KB
comments (?)
stdin 
5 7
1 2
2 1
2 2
2 5
3 2
4 5
5 3
stdout 
4 5 3 2 1
https://ideone.com/xwvGgq
Breadth First Search Traversal with given Adjcency list.
language:
C (gcc 8.3)
created:
4 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!