宽度优先搜索

根据枚举一文中的分析，BFS是一种在状态空间中通过循环求解结点问题的方法。

宽度优先搜索需要借助队列，假设从s开始搜索。

根据对结点进行访问操作的位置，BFS可以分为两种。

(1)访问操作自身：

queue<int> q;
q.push(s); // 从s结点开始搜索

while (!q.empty()) {
    auto t = q.front();
    q.pop();

    if (t到达循环边界 || t满足限界条件) continue;

    // 在此处对t进行层序访问
    
    for (遍历t的所有可能后继y) {
        if (y到达循环边界 || y满足限界条件) continue;

        q.push(y);
    }
}

(2)访问操作后继：

queue<int> q;
// 在此处对s进行层序访问
q.push(s); // 从s结点开始搜索

while (!q.empty()) {
    auto t = q.front();
    q.pop();

    if (t到达循环边界 || t满足限界条件) continue;
    
    for (遍历t的所有可能后继y) {
        if (y到达循环边界 || y满足限界条件) continue;

        // 在此处对y进行层序访问
        q.push(y);
    }
}

注解：BFS算法框架中，判断剪枝条件、判断递归边界、进行访问操作都有两种位置，总结起来区别就是，在扩展后继之前的剪枝条件/递归边界/访问操作是针对自身的，在扩展后继之后的剪枝条件/递归边界/访问操作是针对后继的，详细可以参考枚举。

---