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)
Problem in BFS implementation......Help me please.
Moderator: Board moderators
-
- 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!
-
- Learning poster
- Posts: 96
- Joined: Tue Jul 19, 2011 12:19 pm
- Location: Dhaka, Bangladesh
- 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
Please, help me..........please.
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.
-
- 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:BFS code written by me
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
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!
-
- Learning poster
- Posts: 96
- Joined: Tue Jul 19, 2011 12:19 pm
- Location: Dhaka, Bangladesh
- 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?
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?
-
- 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!