Page 1 of 1

### Problem in BFS implementation......Help me please.

Posted: Sun Dec 09, 2012 2:11 pm
Finding the shortest-path between 1 and 8 in the following graph.
.......................1
..................../.. \...\
................../......\....\
................2........3.....6
.................\....../.......|
...................\../.........|
....................4...........7
....................|...........|
.....................\..........|
......................5......../
........................\...../
...........................8

I can not implement in coding. Please, help me.
Please, help me in the easiest way.(using struct and queue. without pointer, link list)

### Re: Problem in BFS implementation......Help me please.

Posted: Mon Dec 10, 2012 9:15 pm

### Re: Problem in BFS implementation......Help me please.

Posted: Tue Dec 11, 2012 6:50 am
Guru,
I know that's algo. But, I can not implement in coding.
It is better for me if you give me the source code for that example. Then I can learn from your source code.
Guru, If you don't want to publish/public you source code. Please, mail to me:
me.sarker@gmail.com

### Re: Problem in BFS implementation......Help me please.

Posted: Tue Dec 11, 2012 11:37 pm
Input:

Code: Select all

``````8
3 2 3 6
2 1 4
2 1 4
3 2 3 5
2 4 8
2 1 7
2 6 8
2 5 7
1 8``````
BFS code written by me

Code: Select all

``````#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

int n;

void BFS(vector<vector<int> >G, int s, int t) {
queue<int> q;
int p[n+1];
memset(p,0,sizeof(p));
p[s]=-1;
q.push(s);
while(!q.empty()) {
int u=q.front();
q.pop();
if(u==t) break;
for(int v=0;v<G[u].size();v++)
if(p[G[u][v]]==0) {
p[G[u][v]]=u;
q.push(G[u][v]);
}
}
vector<int> v;
v.push_back(t);
while(p[t]!=-1) {
v.push_back(p[t]);
t=p[t];
}
for(int i=v.size()-1;i>=0;i--)
cout << v[i] << endl;
}

int main(void) {
vector<vector<int> > G;
int c, s, t;
cin >> n;
vector<int> v;
G.push_back(v);
for(int i=1;i<=n;i++) {
v.clear();
cin >> c;
while(c--) {
cin >> t;
v.push_back(t);
}
G.push_back(v);
}

cin >> s >> t;
BFS(G,s,t);
return 0;
}``````

### Re: Problem in BFS implementation......Help me please.

Posted: Wed Dec 12, 2012 8:09 am
Guru,
Thanks, Thanks, Thanks...................
Guru,
I cannot understand your sample input.
Because, you take first 2 3 6. Why not 1?
And then 1 4. But why?

### Re: Problem in BFS implementation......Help me please.

Posted: Wed Dec 12, 2012 10:01 pm
That input is a representation of the graph you posted in ASCII art.