广度优先搜索（BFS）代码思路 流程
用于遍历或搜索树或图的算法。从树的根（或图的某个任意节点）开始，探索邻近的节点，然后再移至下一层的邻近节点。
BFS在需要从一个给定的源节点开始搜索最短路径（在未加权的图中）时特别有用。

编写BFS算法代码的基本思路流程可以分为以下步骤：

1. 初始化

• 创建一个队列 Q 用来存储待访问的节点。
• 将起始节点 s 放入队列中。
• 如果需要，创建一个集合或数组 visited 用于跟踪已访问的节点，以避免重复访问。

2. 创建辅助数据结构（如果需要）

• 如果你需要记录额外的信息，比如每个节点的父节点或从源点到每个节点的距离，初始化这些结构。

3. 处理队列中的节点

• 当队列 Q 不为空时 while：
• step++; 开始新一层的遍历，步数加1
• for num 当前层的节点数量
• 从队列中取出一个节点 u 。
• 对于节点 u 的每个邻近节点 vfor：
  • 如果 v 尚未被访问：
  • 标记 v 为已访问（例如，将 v 添加到 visited 中）。
  • 将 v 添加到队列 Q 中。
  • 如果需要，更新辅助数据结构（例如，更新父节点或距离）。

4. 利用辅助数据结构（如果需要）

• 根据算法的需求，利用在遍历过程中收集的数据进行必要的计算，例如，计算最短路径或构建遍历树。

注意事项

• 防止无限循环：确保每个节点只被访问一次，特别是在处理图时，因为图可能包含环。
• 方向性：对于有向图，只考虑从 u 指向 v 的边；对于无向图， u 和 v 之间的边是双向的。
• 加权图：BFS 仅适用于未加权图的最短路径搜索。对于加权图，请考虑使用 Dijkstra 算法或 Bellman-Ford 算法。

#include <iostream>
#include <queue>
using namespace std;

// 假设Node是树节点的结构体，这里只是一个示例
struct Node {
    int val;    // 节点值
    vector<Node*> neighbors;  // 邻居节点
    Node(int x) : val(x) {}
};

// BFS算法实现
int BFS(Node* root, Node* target) {
    if (root == target) return 0; // 如果根节点就是目标节点，则直接返回0
    queue<Node*> queue;  // 用于BFS的队列
    queue.push(root);    // 将根节点加入队列
    int step = 0;        // 从根节点到当前节点的步数
    while (!queue.empty()) {
        step++;          // 开始新一层的遍历，步数加1
        int size = queue.size(); // 当前层的节点数量
        for (int i = 0; i < size; ++i) {
            Node* cur = queue.front(); // 获取当前节点
            queue.pop();               // 从队列中移除当前节点
            for (Node* next : cur->neighbors) { // 遍历当前节点的所有邻居
                if (next == target) return step; // 如果找到目标节点，返回步数
                queue.push(next); // 将邻居节点加入队列
            }
        }
    }
    return -1; // 没有从根节点到目标节点的路径
}

int main() {
    // 示例代码，构建树和调用BFS
    Node* root = new Node(1); // 假设有一个根节点
    Node* target = new Node(2); // 假设有一个目标节点
    // 正常情况下，你需要构建完整的树并设置节点的邻居
    // 这里只是演示如何调用BFS函数
    int result = BFS(root, target);
    cout << "Shortest path length: " << result << endl;
    // 记得释放分配的内存
    delete root;
    delete target;
    return 0;
}