C++广度优先算法实现

下面是C++实现广度优先搜索算法的示例代码：

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

using namespace std;

// 定义节点结构体
struct Node {
    int val;
    vector<Node*> neighbors;
    Node(int _val) : val(_val) {}
};

// 广度优先搜索算法
Node* bfs(Node* start, int target) {
    queue<Node*> q;
    q.push(start);
    unordered_set<Node*> visited;
    visited.insert(start);

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            Node* cur = q.front();
            q.pop();
            if (cur->val == target) {
                return cur;
            }
            for (Node* neighbor : cur->neighbors) {
                if (visited.count(neighbor) == 0) {
                    q.push(neighbor);
                    visited.insert(neighbor);
                }
            }
        }
    }

    return nullptr;
}

int main() {
    // 构造无向图
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    Node* node4 = new Node(4);
    node1->neighbors.push_back(node2);
    node2->neighbors.push_back(node1);
    node2->neighbors.push_back(node3);
    node3->neighbors.push_back(node2);
    node3->neighbors.push_back(node4);
    node4->neighbors.push_back(node3);

    // 调用广度优先搜索算法
    Node* result = bfs(node1, 4);

    // 输出结果
    if (result != nullptr) {
        cout << "Found target node: " << result->val << endl;
    } else {
        cout << "Target node not found." << endl;
    }

    return 0;
}

在上面的示例代码中，我们定义了一个`Node`结构体表示图中的节点，其中包含了一个`val`成员表示节点的值，以及一个`neighbors`成员表示节点的邻居。

我们通过构造无向图来演示广度优先搜索算法的实现，然后调用`bfs`函数进行搜索。在搜索过程中，我们使用一个队列`q`来存储待遍历的节点，使用一个哈希集合`visited`来记录已经访问过的节点，从而避免重复访问。

在每一轮遍历中，我们取出队列中的首个节点`cur`，然后遍历`cur`的所有邻居节点。如果某个邻居节点`neighbor`还没有被访问过，就将其加入到队列`q`中，同时将其标记为已访问。如果`neighbor`的值等于目标值`target`，则直接返回该节点，表示搜索成功。如果队列`q`为空，表示已经遍历完了所有可能的节点，但仍然没有找到目标节点，此时返回`nullptr`，表示搜索失败。