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

[uvasarker]

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]

http://en.wikipedia.org/wiki/Breadth-first_search

[uvasarker]

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]

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;
}

[uvasarker]

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]

That input is a representation of the graph you posted in ASCII art.