树和图的遍历

根据枚举一文中的分析，我们知道对状态空间的枚举不需要考虑自顶向下还是自底向上的问题，但是对于数据空间的遍历，还是有必要区分一下这两种情况。

深度优先

根据访问操作的位置的不同，深度优先遍历可以分为两种。

(1)访问操作自身：

void DFS(int x) {
    if (x到达递归边界 || 满足剪枝条件) return;

    // 在此处对x进行先序访问和更新操作

    for (遍历x的所有可能后继y) {
        if (y到达递归边界 || y满足剪枝条件) continue;

        DFS(y);
    }

    // 后序访问和还原现场
}

DFS(s); // 调用DFS，从s结点开始遍历

(2)访问操作后继：

void DFS(int x) {
    if (x到达递归边界 || x满足剪枝条件) return;

    for (遍历x的所有可能后继y) {
        if (y到达递归边界 || y满足剪枝条件) continue;

        // 在此处对y进行先序访问和更新操作
        DFS(y);
        // 后序访问和还原现场
    }
}

// 在此处对s进行先序访问和更新操作
DFS(s); // 调用DFS，从s结点开始遍历
// 后序访问和还原现场

注解：

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

(2)要实现自顶向下的深度优先遍历，在算法框架中只写先序访问部分的代码，不写后序访问部分的代码即可；同理，要实现自底向上的深度优先遍历，在算法框架中只写后序访问部分的代码，不写先序访问部分的代码即可。

广度优先

根据访问操作的位置的不同，广度优先遍历可以分为两种。

(1)访问操作自身：

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

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

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

    // 在此处对t进行层序访问和更新操作
    
    for (遍历t的所有可能后继y) {
        if (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);
    }
}

注解：

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

(2)上面介绍的算法框架只能实现自顶向下的广度优先遍历，这里再介绍另外一种写法，这种写法中既能实现自顶向下，又能实现自底向上的广度优先遍历。

将遍历改为用内、外两层循环实现，内循环用来遍历一层中的所有结点，这样每一次外循环就不再是对应一个结点，而是对应一层结点：

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

while (!q.empty()) {  // 外循环
    int size = q.size();
    for (int i = 0; i < size; i++) {  // 内循环  
        auto t = q.front();
        q.pop();

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

        // 在此处对t进行层序访问和更新操作
    
        for (遍历t的所有可能后继y) {
            if (y到达递归边界 || 满足剪枝条件) continue;

            q.push(y);
        }
    }
}

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

while (!q.empty()) {  // 外循环
    int size = q.size();
    for (int i = 0; i < size; i++) {  // 内循环
        auto t = q.front();
        q.pop();

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

            // 在此处对y进行层序访问和更新操作
            q.push(y);
        }
    }
}

我们将每一次外循环中遍历到的结点存储在一个序列中，这个序列就是一层结点从左到右的序列。再在外循环外部用一个总序列表示广度优先遍历的序列，如果每次将一层结点序列添加到总序列的尾部，总序列就是自顶向下的，如果每次将一层结点序列添加到总序列的头部，总序列就是自底向上的。

---