# BFS concepts, search in a Graph

Asked By 260 points N/A Posted on -

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
Answered By 0 points N/A #92856

## 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.

OnÂ reading this, you shall also realize the application of queues inÂ BFS.
Â
Answered By 260 points N/A #92857

## 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]);
Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â  }Â Â Â Â Â Â Â Â Â Â Â
Â Â Â Â Â Â Â  }
Â  Â

Answered By 0 points N/A #92858

## 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

boolÂ visit[mxNod];

Then you can just use this small function to get the adjacent nodes

Â Â Â  {
Â Â Â Â Â Â Â Â 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

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

Answered By 0 points N/A #92860

## BFS concepts, search in a Graph

Answered By 260 points N/A #92861

## BFS concepts, search in a Graph

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

You are most welcome.