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

General topic about Valladolid Online Judge

Moderator: Board moderators

Post Reply
uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Location: Dhaka, Bangladesh
Contact:

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

Post by uvasarker » Sun Dec 09, 2012 2:11 pm

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.

Post by brianfry713 » Mon Dec 10, 2012 9:15 pm

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

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

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

Post by uvasarker » 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
Please, help me..........please.

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.

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

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

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

Post by uvasarker » 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?

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.

Post by brianfry713 » Wed Dec 12, 2012 10:01 pm

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

Post Reply

Return to “General”