Search code examples
c++breadth-first-search

Why is a 1 being printed at the end of BFS?


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

Solution

  • 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).