bfs

kazi_omar

Mar 11th, 2021

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 1.67 KB | None | 0 0

raw download clone embed print report

#include <bits/stdc++.h>
using namespace std;
int bfs(int s, int dest, int node, vector<int> v[])
{
int vis[node + 1];
memset(vis, -1, sizeof(vis));
queue<int> q;
q.push(s);
vis[s] = 0;
int peak = 0;
while (!q.empty())
{
peak = q.front();
// cout << "parent: " << q.front() << "; not visited child: ";
q.pop();
for (int i = 0; i < v[peak].size(); i++)
{
if (vis[v[peak][i]] == -1)
{
// cout << v[peak][i] << " ";
vis[v[peak][i]] = vis[peak] + 1;
q.push(v[peak][i]);
// if (i == v[peak].size() - 1)
// {
// cout << "; dis from "
// << "source " << s << ": " << vis[peak] + 1;
// }
}
}
// cout << endl;
}
return vis[dest];
}
int main()
{
int node, edge;
// cout << "path from source --> destination: " << endl;
cin >> node >> edge;
vector<int> v[node + 1];
int s, d;
for (int i = 0; i < edge; i++)
{
cin >> s >> d;
v[s].push_back(d);
v[d].push_back(s);
}
// for (int i = 1; i <= node; i++)
// {
// cout << i << "--> ";
// for (int j = 0; j < v[i].size(); j++)
// {
// cout << v[i][j] << " ";
// }
// cout << endl;
// }
// cout << endl;
int source, dest;
cin >> source >> dest;
// cout << "min distance from source " << source << " to " << dest << ": " << endl;
cout << bfs(source, dest, node, v);
return 0;
}

Add Comment

Please, Sign In to add comment