aidul23

From BFS traversal print the path of a source vertex to any arbitrary vertex

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