Here's a simple Breadth First Search on an undirected graph.
The question is to find whether or not a path exists between a source and a destination node. The code works, but I don't understand why a 1
is being printed at the very end.
Program:
#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
bool BFS(unordered_map<int, vector<int>> &umap, int source, int dest) {
queue<int> q;
vector<int> v;
q.push(source);
while (!q.empty()) {
int front = q.front();
if (find(v.begin(), v.end(), front) == v.end()) {//element is not visited yet
cout << static_cast<char>(front) << " -> ";
if (front == dest)
return true;
v.push_back(front);
for (auto &i: umap[front])
q.push(i);
}
q.pop();
}
return false;
}
int main() {
unordered_map<int, vector<int>> umap;
umap['i'] = {'j', 'k'};
umap['j'] = {'i'};
umap['k'] = {'i', 'm', 'p'};
umap['m'] = {'k'};
umap['p'] = {'k'};
umap['o'] = {'n'};
umap['n'] = {'o'};
cout << endl
<< "------------BFS------------"
<< endl;
cout << BFS(umap, 'j', 'm');
}
Output:
------------BFS------------
j -> i -> k -> m -> 1
Process finished with exit code 0
The first comment on this question sums it up - I overlooked the fact that I am printing a bool
(cout << BFS(umap, 'j', 'm');
), so a 1
is expected in this case where a path is found (the value is true
).