深度优先搜索

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

深度优先搜索需要借助栈，不过真正实现时一般使用递归，假设从s结点开始搜索。

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

(1)访问操作自身：

void DFS(int x) {
    if (x到达递归边界 || 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结点开始搜索
// 后序访问

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

---