这个广度优先搜索的实现有什么问题？

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

您可以越界访问 adj。它的大小为 4，但在 addEdge(adj, 3, 4); 中，您正在写入第 4 个元素（在基于 1 的索引中为第 5 个元素）。
条件if (!visited[i])没有意义。 i 应替换为下一个节点索引，即 adjList[cur][i].

这个广度优先搜索的实现有什么问题？

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

c++

graph

breadth-first-search

graph-algorithm