aidul23

Find out the Connected Components of a graph using BFS

Aug 30th, 2020
219
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.28 KB | None | 0 0
  1. #include<stdio.h>
  2. int a[20][20], q[20], visited[20], n,u, 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. void isConnectedGraph(int v,int u)
  16. {
  17.     for(i = 1; i <= n; i++)
  18.         if(a[v][u] && !visited[i])
  19.             q[++r] = i;
  20.     if(f <= r)
  21.     {
  22.         visited[q[f]] = 1;
  23.         bfs(q[f++]);
  24.     }
  25. }
  26.  
  27. void main()
  28. {
  29.     int v;
  30.     printf("\n Enter the number of vertices:");
  31.     scanf("%d", &n);
  32.  
  33.  
  34.     for(i=1; i <= n; i++)
  35.     {
  36.         q[i] = 0;
  37.         visited[i] = 0;
  38.     }
  39.  
  40.     printf("\n Enter graph data in matrix form:\n");
  41.     for(i=1; i<=n; i++)
  42.     {
  43.         for(j=1; j<=n; j++)
  44.         {
  45.             scanf("%d", &a[i][j]);
  46.         }
  47.     }
  48.  
  49.     printf("\n Enter the starting vertex:");
  50.     scanf("%d", &v);
  51.     bfs(v);
  52.     printf("\n Enter the ending vertex:");
  53.     scanf("%d", &u);
  54.     isConnectedGraph(v,u);
  55.     printf("\n The node's  traversal path:\n");
  56.  
  57.  
  58.     for(i=1; i <= n; i++)
  59.     {
  60.         if (a[i][u] == 1 && visited[i] == 0)
  61.         {
  62.             for(j=1; j<=n; j++)
  63.                 visited[i] =1;
  64.             printf("%d\t", a[i][j]);
  65.         }
  66.     }
  67. }
Add Comment
Please, Sign In to add comment