BFS concepts, search in a Graph

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.

• Status: Open
• Question Views: 1153
• Answer Count: 7
• Vote Up 26 Vote Down

• Answer Accepted: Yes
• Question Category: C++

Best Answer by softwaresynthesis

Go To Solution

Answered By softwaresynthesis 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.

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.

About softwaresynthesis

Questions
0

Answers
25

Best Answers
6

• Vote Up 0 Vote Down

• Posted on - 05/13/2011
• Question Category: C++

Answered By Tech Martin 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]);
                }           
        }
   

I have no idea how to apply it! Please help.

About Tech Martin

Questions
1

Answers
3

Best Answers
0

• Vote Up 0 Vote Down

• Posted on - 05/13/2011
• Question Category: C++

Answered By softwaresynthesis 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

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.

About softwaresynthesis

Questions
0

Answers
25

Best Answers
6

• Vote Up 0 Vote Down

• Posted on - 05/13/2011
• Question Category: C++

Answered By Tech Martin 260 points N/A #92859

BFS concepts, search in a Graph

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

About Tech Martin

Questions
1

Answers
3

Best Answers
0

• Vote Up 0 Vote Down

• Posted on - 05/13/2011
• Question Category: C++

Best Answer

Best Answer

Answered By softwaresynthesis 0 points N/A #92860

BFS concepts, search in a Graph

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

About softwaresynthesis

Questions
0

Answers
25

Best Answers
6

• Vote Up 0 Vote Down

• Posted on - 05/13/2011
• Question Category: C++

Answered By Tech Martin 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.

About Tech Martin

Questions
1

Answers
3

Best Answers
0

• Vote Up 0 Vote Down

• Posted on - 05/13/2011
• Question Category: C++

Answered By softwaresynthesis 0 points N/A #92862

BFS concepts, search in a Graph

You are most welcome.

About softwaresynthesis

Questions
0

Answers
25

Best Answers
6

• Vote Up 0 Vote Down

• Posted on - 05/13/2011
• Question Category: C++