BFS concepts, search in a Graph

Asked By 260 points N/A Posted on -
qa-featured

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.

SHARE
Best Answer by softwaresynthesis
Answered By 0 points N/A #92856

BFS concepts, search in a Graph

qa-featured

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.
Answered By 260 points N/A #92857

BFS concepts, search in a Graph

qa-featured

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.

Answered By 0 points N/A #92858

BFS concepts, search in a Graph

qa-featured

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.

Answered By 260 points N/A #92859

BFS concepts, search in a Graph

qa-featured

Thanks, but my code gives: error: 'queue' was not declared in this scope.

Best Answer
Best Answer
Answered By 0 points N/A #92860

BFS concepts, search in a Graph

qa-featured

Header file missing. Did you #include<queue> on your code?

Answered By 260 points N/A #92861

BFS concepts, search in a Graph

qa-featured

Cool,

I don't know how to thank you synthesis. That was very nice of you.

Answered By 0 points N/A #92862

BFS concepts, search in a Graph

qa-featured

You are most welcome.

Related Questions