CODEWITHSUNDEEP
c++graphgraph-algorithmbreadth-first-search
arujbansal
arujbansal

Reputation: 117

What's wrong with this implementation of Breadth First Search?

Here is my whole program:

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void addEdge(vector<int> adjList[], int u, int v) {
    adjList[u].push_back(v);
    adjList[v].push_back(u);
}

void bfs(int s, vector<int> adjList[], vector<bool> visited, int V) {
    queue<int> q;
    q.push(s);
    visited[s] = true;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        cout << cur << " ";
        for (int i = 0; i < adjList[cur].size(); i++) {
            if (!visited[i]) {
                q.push(adjList[cur][i]);
                visited[i] = true;
            }
        }
    }
}

int main() {
    int V = 4;
    vector<int> adj[4];
    vector<bool> visited;
    visited.assign(V, false);
    addEdge(adj, 0, 1);
    addEdge(adj, 2, 3);
    addEdge(adj, 3, 4);
    bfs(0, adj, visited, V);
    return 0;
}

I want to perform Breadth First Search (BFS) and print out nodes as they are discovered. For some reason this isn't printing anything. What have I done wrong?

Upvotes: 0

Views: 53

Answers (1)

Evg
Evg

Reputation: 26272

  1. You have out-of-bounds access to adj. It has size 4, but in addEdge(adj, 3, 4); you're writing into the 4-th element (5-th in one-based indexing).

  2. The condition if (!visited[i]) doesn't make sense. i should be replaced with the next node index, i.e. adjList[cur][i].

Upvotes: 2

Related Questions