here is only basic implementation of problems for beginners. If you have any problem with any solution or any basic concept of programming or you want more efficient solution you can mail me.
my suggestion is not to copy and paste codes from here try to understand the logic and think why you were not able to solve it.
Showing posts with label bfs. Show all posts
Showing posts with label bfs. Show all posts

Wednesday, 22 October 2014

Breadth first traversal for undirected graph

here we are assuming that all the nodes are connected


#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
void bfs(vector<int> ar[],int visited[],int i,int n){
  int j;
  queue<int> que;
  visited[i]=1;
  que.push(i);
  while(que.size()>0){
   i=que.front();
   que.pop();
   printf("%d\n",i);
   for(j=0;j<ar[i].size();j++){
          if(visited[ar[i][j]]==0){
              que.push(ar[i][j]);
              visited[ar[i][j]]=1;
          }
      }
  }

}
int main(){
  int a,b,i,j,n,m;
  printf("no of nodes\n");
  scanf("%d",&n);
  vector<int> ar[n+9];
  int visited[n+9];
  for(i=0;i<n+9;i++){
    visited[i]=0;
   }
   printf("no of edges\n");
   scanf("%d",&m);
   printf("Enter edges\n");
   for(j=0;j<m;j++){
     scanf("%d %d",&a,&b);
     ar[a].push_back(b);
     ar[b].push_back(a);
   }
   printf("from which node to traverse\n");
   scanf("%d",&i);
   bfs(ar,visited,i,n);
  return 0;
}