aidul23

Implement BFS Traversal and print the traversal path

Aug 30th, 2020
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.81 KB | None | 0 0
  1. #include<stdio.h>
  2. int a[20][20], q[20], visited[20], n, i, j, f = 0, r = -1;
  3.  
  4. void bfs(int v) {
  5.  for(i = 1; i <= n; i++)
  6.  if(a[v][i] && !visited[i])
  7.  q[++r] = i;
  8.  if(f <= r) {
  9.  visited[q[f]] = 1;
  10.  bfs(q[f++]);
  11.  }
  12. }
  13.  
  14. void main() {
  15.  int v;
  16.  printf("\n Enter the number of vertices:");
  17.  scanf("%d", &n);
  18.  
  19.  
  20.  for(i=1; i <= n; i++) {
  21.  q[i] = 0;
  22.  visited[i] = 0;
  23.  }
  24.  
  25.  printf("\n Enter graph data in matrix form:\n");
  26.  for(i=1; i<=n; i++) {
  27.  for(j=1;j<=n;j++) {
  28.  scanf("%d", &a[i][j]);
  29.  }
  30.  }
  31.  
  32.  printf("\n Enter the starting vertex:");
  33.  scanf("%d", &v);
  34.  bfs(v);
  35.  printf("\n The node's  traversal path:\n");
  36.  
  37.  for(i=1; i <= n; i++) {
  38.  if(visited[i])
  39.  for(j=1;j<=n;j++) {
  40.  printf("%d\t", a[i][j]);
  41.  }else {
  42.  printf("\n Bfs is not possible. Not all nodes are reachable");
  43.  break;
  44.  }
  45.  }
  46. }
Add Comment
Please, Sign In to add comment