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

Moderator: Board moderators

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Contact:

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

I want to learn graph theory. Please me, please.
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)

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

Check input and AC output for thousands of problems on uDebug!

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Contact:

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

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

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;
}``````
Check input and AC output for thousands of problems on uDebug!

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Contact:

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

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?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

That input is a representation of the graph you posted in ASCII art.
Check input and AC output for thousands of problems on uDebug!