naeem043

C & C++ BFS

May 25th, 2018
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.59 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <queue>
  3.  
  4. using namespace std;
  5.  
  6. int g[7][7],color[7],prev[7],d[7];
  7.  
  8. void BFS(int g[7][7])
  9. {
  10.     int i,j,s=0,u,v;
  11.     queue <int> q;
  12.  
  13.    for(i=0;i<7;i++)
  14.     {
  15.         color[i] = 0;
  16.         prev[i] = 0;
  17.         d[i] = 999999;
  18.     }
  19.  
  20.     color[s] = 0;
  21.     prev[s] = 0;
  22.     d[s] = 0;
  23.     q.push(s);
  24.  
  25.     while(!q.empty())
  26.     {
  27.         u = q.front();
  28.         q.pop();
  29.  
  30.        for(i=0;i<7;i++)
  31.         {
  32.             if(color[i]==0 && g[u][i] !=0)
  33.             {
  34.                 color[i] = 1;
  35.                 d[i] = d[u]+1;
  36.                 prev[i] = u;
  37.                 q.push(i);
  38.             }
  39.  
  40.         }
  41.  
  42.         color[u] = 2;
  43.     }
  44.     printf("\n d:\t");
  45.     for(i=0;i<7;i++)
  46.         printf("%d",d[i]);
  47.  
  48.     printf("\n color:\t");
  49.     for(i=0;i<7;i++)
  50.         printf("%d",color[i]);
  51.  
  52.  
  53.     printf("\n prev:\t");
  54.     for(i=0;i<7;i++)
  55.         printf("%d",prev[i]);
  56.  
  57. }
  58.  
  59. int main()
  60. {
  61.     int i,j;
  62.  
  63.     for(i=0;i<7;i++)
  64.     {
  65.          for(j=0;j<7;j++)
  66.          {
  67.              g[i][j] = 0;
  68.          }
  69.  
  70.     }
  71. // Graph initialize
  72.     g[0][1] = 1;
  73.     g[0][2] = 1;
  74.     g[0][3] = 1;
  75.  
  76.     g[1][0] = 1;
  77.     g[1][3] = 1;
  78.     g[1][5] = 1;
  79.  
  80.     g[2][0] = 1;
  81.     g[2][4] = 1;
  82.     g[2][6] = 1;
  83.  
  84.     g[3][0] = 1;
  85.     g[3][1] = 1;
  86.     g[3][6] = 1;
  87.  
  88.     g[4][2] = 1;
  89.  
  90.     g[5][1] = 1;
  91.     g[5][6] = 1;
  92.  
  93.     g[6][2] = 1;
  94.     g[6][3] = 1;
  95.     g[6][5] = 1;
  96.  
  97.     for(i=0;i<7;i++)
  98.     {
  99.        for(j=0;j<7;j++)
  100.        {
  101.            printf("%d ",g[i][j]);
  102.        }
  103.         printf("\n");
  104.     }
  105.  
  106.     BFS(g);
  107.     return 0;
  108. }
Add Comment
Please, Sign In to add comment