Pages

Breath-First-Search(BFS) Source Code without using Queue :)

29 July 2013
 Implementation BFS algorithm using C++
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
#define M 10000
vector<int> edges[M];
//vector<int> cost[M];                     // u can use it later

void Bfs(int n,int source)                  // number of nodes and source point(node)
{

    vector<int> v1,v2;             // declare 2 vector instead of queue
    v1.push_back(source);     
    int taken[100]={0};
    printf("Level 0 :: %d\n",source);
    for(int loop=1;loop<n;loop++)
    {

        printf("Level %d ::",loop);
        for(int i=0;i<v1.size();i++)
        {

            int u=v1[i];
            for(int j=0;j<edges[u].size();j++)
            {
                int v=edges[u][j];               // we found an edge from u to v
                if(!taken[v])                    // we can not go same node twice
                   { printf("%d ",v);          // just process
                    taken[v]=1;                // processed an edge and puts a tag
                    v2.push_back(v);         // where we found v1's node and push it v2
                }
            }
        }

        if(v2.empty())
        {puts("Empty");break;         // can not process any more
        }
        else{                                 // process again
            puts("");
            v1.clear();
            v1=v2;
            v2.clear();
        }
    }
}



int main()
{
    int N,E,i;
    int esize,source;                      // esize==edge size
    scanf("%d%d",&N,&E);       //how many nodes and edges
    for(i=1;i<=E;i++)
       {
           int x,y;
           scanf("%d%d",&x,&y);
           edges[x].push_back(y);
           edges[y].push_back(x);
          // cost[x].push_back(1);       // we can use it future
          // cost[y].push_back(1);        // we can use it future
       }
printf("plz enter source node:");
scanf("%d",&source);
       Bfs(N,source);
 
       return 0;
}
// i followed this code by shafayet's lecture....Thanks shafayet :)

No comments:

Post a Comment