Что не так с этой реализацией поиска в ширину?

Question

Вот вся моя программа:

#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;
}

Я хочу выполнить поиск в ширину (BFS) и распечатывать узлы по мере их обнаружения. По какой-то причине это ничего не печатает. Что я сделал не так?

Answer 1

1. У вас есть нерегулярный доступ к adj. Он имеет размер 4, но в addEdge(adj, 3, 4); вы записываете в 4-й элемент (5-й в индексации по одному основанию).

2. Условие if (!visited[i]) не имеет смысла. i должен быть заменен следующим индексом узла, т.е. adjList[cur][i].