Advertisement
Riz1Ahmed

BFS With Adjacency List & Matrix

Feb 19th, 2019
176
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include <cstdio>
  2. #include <vector>
  3. #include <map>
  4. #include <queue>
  5. using namespace std;
  6. int main(){
  7.     int n,e,u,v,i,j;
  8.     printf("Input Node and Vertex size: ");
  9.     scanf("%d %d",&n,&e);
  10.     printf("Input the Vertices:\n");
  11.     vector<int> list[n+5];
  12.     map<int,int>matrix[n+5];
  13.     for (i=0; i<e; i++){
  14.         scanf("%d %d",&u,&v);
  15.         list[u].push_back(v);
  16.         list[v].push_back(u);
  17.         matrix[u][v]=1;
  18.         matrix[v][u]=1;
  19.     }
  20.     printf("\nAdjusency List.\n");
  21.     for (i=0; i<=n; i++){
  22.         if (!list[i].empty()){
  23.             printf("%d=",i);
  24.             for (j=0; j<list[i].size();j++)
  25.                 printf(" %d",list[i][j]);
  26.             puts("");
  27.         }
  28.     }
  29.     printf("\nAdjusency Matrix.\n");
  30.     for (i=0; i<=n; i++){
  31.         for (j=0; j<=n;j++)
  32.             printf(" %d",matrix[i][j]);
  33.         puts("");
  34.     }
  35.     printf("\nBFS from %d.\n",u);
  36.     int vis[n+2];
  37.     memset(vis,0,sizeof vis);
  38.     queue<int>q;
  39.     q.push(u); ///Start from u.
  40.     vis[u]=1;
  41.     while (!q.empty()){
  42.         u=q.front(); q.pop();
  43.         printf("%d ",u);
  44.         int c=(vis[u]==1 ? 2:1); ///for Bicoloring
  45.         for (i=0; i<list[u].size(); i++){
  46.             v=list[u][i];
  47.             if (!vis[v]){
  48.                 vis[v]=c;
  49.                 q.push(v);
  50.             }
  51.             /*else if (vis[y]!=c){
  52.                 printf("Impossible bicoloring.\n");
  53.                 break;
  54.             }*/
  55.         }
  56.     } return !puts("");
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement