宽度优先搜索（Breadth-First Search，BFS）是一种遍历或搜索树和图的算法，它从一个节点开始，逐层遍历节点，即先访问起始节点的所有邻接节点，再访问邻接节点的邻接节点，依此类推。BFS常用于寻找最短路径，或在层次化结构中按层次顺序访问节点。

宽度优先搜索的特点：

• 层序遍历：BFS按层序顺序访问图中的所有顶点。
• 队列的使用：BFS通常使用队列来存储待访问的节点。
• 最短路径：在未加权图中，BFS可以找到从源节点到其他所有节点的最短路径。

宽度优先搜索的实现：

使用队列的实现

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

void BFS(int start, const std::vector<std::vector<int>>& graph) {
    std::vector<bool> visited(graph.size(), false);
    std::queue<int> queue;

    visited[start] = true;
    queue.push(start);

    while (!queue.empty()) {
        int v = queue.front();
        queue.pop();

        std::cout << "访问节点：" << v << std::endl;

        for (int neighbor : graph[v]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.push(neighbor);
            }
        }
    }
}

BFS在图中的应用

int main() {
    int V = 5; // 假设有5个顶点
    std::vector<std::vector<int>> graph(V); // 创建邻接表

    // 假设添加了一些边
    graph[0].push_back(1);
    graph[0].push_back(2);
    graph[1].push_back(0);
    graph[1].push_back(2);
    graph[2].push_back(0);
    graph[2].push_back(1);
    graph[2].push_back(3);
    graph[3].push_back(2);
    graph[3].push_back(4);
    graph[4].push_back(3);

    BFS(0, graph); // 从顶点0开始宽度优先搜索

    return 0;
}

宽度优先搜索的应用：

• 最短路径：在未加权图中，BFS可以用来找到从源节点到其他所有节点的最短路径。
• 社交网络分析：在社交网络中，BFS可以用来找到个体之间的最短联系路径。
• 网络搜索：在网络爬虫中，BFS可以用于从起始页面开始，逐层抓取网页。
• 迷宫求解：在迷宫问题中，BFS可以用来找到从起点到终点的最短路径。

变种：带权重的BFS

在有权图中，BFS可以被修改以支持带权重的最短路径搜索，例如在Dijkstra算法中，通过优先队列（通常是最小堆）来选择下一个节点。

宽度优先搜索是一种基础而强大的算法，适用于多种场景，特别是在需要按层序或寻找最短路径时。