用c++实现广度优先搜索算法

在C++中，广度优先搜索（Breadth-First Search, BFS）算法通常用于查找图或树中的最短路径。以下是使用邻接矩阵或邻接列表实现BFS的基本步骤：

**使用邻接矩阵：**
1. 创建一个队列和一个布尔数组标记节点是否已访问。
2. 将起始节点（源）入队。
3. 对于队列中的每个节点，访问它并标记为已访问。
4. 从当前节点的邻居（矩阵下标对应的行和列）中找出未访问的节点，将它们加入队列。
5. 重复步骤3-4，直到队列为空，或者找到目标节点。

**使用邻接列表：**
1. 创建一个队列和一个集合（或vector<bool>）标记节点是否已访问。
2. 将起始节点入队。
3. 对于队列中的每个节点，访问它并标记为已访问。
4. 遍历当前节点的所有邻居，将未访问的邻居加入队列。
5. 重复步骤3-4，直到队列为空，或者找到目标节点。

**代码示例（邻接列表）：**

#include <iostream>
#include <queue>
#include <unordered_set>

// 图的邻接列表表示
using namespace std;
struct Node {
    int id;
    vector<int> neighbors;
};

void bfs(Node* start, int target) {
    queue<Node*> q;
    unordered_set<Node*> visited;
    q.push(start);
    visited.insert(start);

    while (!q.empty()) {
        Node* current = q.front();
        q.pop();

        if (current->id == target) {
            cout << "Target node found: " << target << endl;
            return;
        }

        for (int neighbor : current->neighbors) {
            if (visited.find(neighbor) == visited.end()) {
                q.push(neighbor);
                visited.insert(neighbor);
            }
        }
    }
    cout << "Target node not found." << endl;
}

int main() {
    // 初始化图数据结构...
    Node start_node = {0, {1, 2, 3}};
    Node target_node = {7, {}}; // 假设目标节点ID为7
    bfs(&start_node, target_node.id);
    return 0;
}