Asked By
Tech Martin
260 points
N/A
Posted on - 05/13/2011
Hi.
I am trying to understand this code:
q.push(start);
       Visit [start] =1;
        while(!q.empty())
       {
           cur=q.front();
            q.pop();
            process(cur);
            adjacents=get_adjacent of(cur);
            fo(i,0,sz(adjacents))
                if(visit[adjacent[i]]==0)
               {
                    visit[adjacent[i]]=1;
                    q.push(adjacent[i]);
               }          Â
       }
Doing some BFS search. But I don't see anything that matches the text book. As far as I understood the BFS traversing searches the parent first and then from left to right the child nodes. If not found, then the leftmost becomes the parent doing the same thing.
The process continues until the Node is found. But how do I do it? Please explain the process if possible.
BFS concepts, search in a Graph
Hello Martin,
If you have a confusion about the BFS concept, then I would suggest you to first understand it properly.
Here is a nice presentation on it.
On reading this, you shall also realize the application of queues in BFS.
Â
This will help you understand the code I believe.
BFS concepts, search in a Graph
Thanks a lot.
I am clear on the concept now. But how do I apply it in the code? Will this be the algorithm something like:
       q.push(start);
       Visit [start] =1;
        while(!q.empty())
       {
           cur=q.front();
            q.pop();
            process(cur);
            adjacents=get_adjacent of(cur);
            fo(i,0,sz(adjacents))
                if(visit[adjacent[i]]==0)
               {
                    visit[adjacent[i]]=1;
                    q.push(adjacent[i]);
               }          Â
       }
 Â
I have no idea how to apply it! Please help.
BFS concepts, search in a Graph
It should not be much of a trouble; C++Â STLÂ is very handy for this.
Use an array of vector to store the graph as adjacency matrix and keep an array for tracking visits nodes, like
vector<int>Â adjList[mxNod];
bool visit[mxNod];
Then you can just use this small function to get the adjacent nodes
vector<int> get_adj(int c)
   {
        return adjList[c];
   }
So your code should look something like:
void bfsGraph(int start)
   {
        init();
        queue <int> q;
        q.push(start);
        visit[start]=1;
        while(!q.empty())
       {
            int cur=q.front();
            q.pop();
            process(cur);
            vector<int> adj=get_adj(cur);
            for(int i=0;i<adj.size();i++)
           {
                if(visit[adj[i]]==0)
               {
                    visit[adj[i]]=1;
                    q.push(adj[i]);
               }
           }
       }
   }
Hope this helps.
BFS concepts, search in a Graph
Thanks, but my code gives:Â error: 'queue' was not declared in this scope.
BFS concepts, search in a Graph
Header file missing. Did you #include<queue> on your code?
BFS concepts, search in a Graph
Cool,
I don't know how to thank you synthesis. That was very nice of you.
