C++广度优先搜索算法实现(附代码示例)

广度优先搜索（BFS）是一种常用的图遍历算法，本文将介绍如何使用C++实现BFS算法，并提供详细的代码示例。

代码实现cpp#include #include #include <unordered_set>#include

// 定义图的邻接表表示using Graph = std::vector<std::vector>;

void bfs(const Graph& graph, int start) { std::queue queue; std::unordered_set visited;

queue.push(start);    visited.insert(start);

while (!queue.empty()) {        int node = queue.front();        queue.pop();        std::cout << node << ' '; // 对节点进行处理，这里只是简单地打印节点

    for (int neighbor : graph[node]) {            if (visited.count(neighbor) == 0) { // 如果邻居节点未被访问过                queue.push(neighbor);                visited.insert(neighbor);            }        }    }}

int main() { // 构建图的邻接表表示 Graph graph = { {1, 2}, // 节点0的邻居节点 {0, 2, 3}, // 节点1的邻居节点 {0, 1, 3}, // 节点2的邻居节点 {1, 2, 4}, // 节点3的邻居节点 {3} // 节点4的邻居节点 };

int startNode = 0;    bfs(graph, startNode);

return 0;}

代码解析

图的表示: 代码中使用std::vector<std::vector<int>>来表示图的邻接表。2. BFS函数: bfs函数接受图和起始节点作为参数，使用队列存储待访问的节点，使用std::unordered_set记录已访问的节点，防止重复访问。3. 遍历过程: 从起始节点开始，将其入队并标记为已访问。循环遍历队列，每次取出队首节点，访问其所有未被访问的邻居节点，并将它们入队并标记为已访问。4. 示例: 代码中构建了一个简单的图，并从节点0开始进行广度优先搜索，输出遍历顺序。

总结

本文介绍了如何使用C++实现广度优先搜索算法，并提供了详细的代码示例。你可以根据具体问题的需求修改和扩展代码。