Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <queue>
- using namespace std;
- int g[7][7],color[7],prev[7],d[7];
- void BFS(int g[7][7])
- {
- int i,j,s=0,u,v;
- queue <int> q;
- for(i=0;i<7;i++)
- {
- color[i] = 0;
- prev[i] = 0;
- d[i] = 999999;
- }
- color[s] = 0;
- prev[s] = 0;
- d[s] = 0;
- q.push(s);
- while(!q.empty())
- {
- u = q.front();
- q.pop();
- for(i=0;i<7;i++)
- {
- if(color[i]==0 && g[u][i] !=0)
- {
- color[i] = 1;
- d[i] = d[u]+1;
- prev[i] = u;
- q.push(i);
- }
- }
- color[u] = 2;
- }
- printf("\n d:\t");
- for(i=0;i<7;i++)
- printf("%d",d[i]);
- printf("\n color:\t");
- for(i=0;i<7;i++)
- printf("%d",color[i]);
- printf("\n prev:\t");
- for(i=0;i<7;i++)
- printf("%d",prev[i]);
- }
- int main()
- {
- int i,j;
- for(i=0;i<7;i++)
- {
- for(j=0;j<7;j++)
- {
- g[i][j] = 0;
- }
- }
- // Graph initialize
- g[0][1] = 1;
- g[0][2] = 1;
- g[0][3] = 1;
- g[1][0] = 1;
- g[1][3] = 1;
- g[1][5] = 1;
- g[2][0] = 1;
- g[2][4] = 1;
- g[2][6] = 1;
- g[3][0] = 1;
- g[3][1] = 1;
- g[3][6] = 1;
- g[4][2] = 1;
- g[5][1] = 1;
- g[5][6] = 1;
- g[6][2] = 1;
- g[6][3] = 1;
- g[6][5] = 1;
- for(i=0;i<7;i++)
- {
- for(j=0;j<7;j++)
- {
- printf("%d ",g[i][j]);
- }
- printf("\n");
- }
- BFS(g);
- return 0;
- }
Add Comment
Please, Sign In to add comment