图算法：广度优先搜索 (BFS)

什么是广度优先搜索？

广度优先搜索（BFS）是另一种用于遍历或搜索树或图的算法。它从根（或任意起始节点）开始，探索邻居节点，然后再逐层探索下一级的邻居节点。

算法思想

BFS 的核心是队列。

1. 创建一个队列，并将起始节点放入队列中。
2. 将起始节点标记为已访问。
3. 当队列不为空时，循环执行： a. 从队列中取出一个节点 u。 b. 访问 u 的所有未被访问的邻居节点。 c. 将这些邻居节点加入队列，并标记为已访问。

代码实现 (C++)

#include <iostream>
#include <vector>
#include <map>
#include <list>
#include <queue>

class Graph {
    std::map<int, std::list<int>> adj;

public:
    void addEdge(int v, int w);
    void BFS(int s);
};

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
}

void Graph::BFS(int s) {
    std::map<int, bool> visited;
    std::queue<int> queue;

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

    while(!queue.empty()) {
        s = queue.front();
        std::cout << s << " ";
        queue.pop();

        for (auto i = adj[s].begin(); i != adj[s].end(); ++i) {
            if (!visited[*i]) {
                visited[*i] = true;
                queue.push(*i);
            }
        }
    }
}

应用场景

• 寻找图中两个节点之间的最短路径（在无权图中）。
• 层序遍历。
• 在社交网络中寻找“K度好友”。