DFS

DFS(深度优先搜索)是一种图论算法，它通过深度优先的顺序遍历图中的所有节点。DFS算法从一个起始节点开始，不断沿着边往下搜索，直到遇到终止节点或无法继续搜索为止。

DFS算法的实现可以使用递归或使用栈来实现。递归实现中，每个节点会被搜索一次，并且在搜索完之后会被弹出。而使用栈来实现时，每个节点会被压入栈中，直到所有的节点都被搜索完。

DFS算法常用于下面的场景：

1. 求图中的连通块
2. 检测图中是否有环
3. 求图中的桥
4. 求图的生成树
5. 求图的拓扑排序
6. 求两点之间的路径

在DFS算法中，可能会出现搜索过程中无用结点的情况，这些无用结点会增加搜索时间复杂度，降低算法效率。这就是剪枝技术的用处。

剪枝技术通过在搜索过程中，对某些结点进行剪枝，减少不必要的搜索，提高算法的效率。

下面列举常见的几种剪枝技巧：

1. 回溯法剪枝：在搜索过程中，记录当前结点已经搜索过的结点，遇到已经搜索过的结点时直接返回，不再进行搜索，可以使用哈希表或者数组来维护已经搜索过的结点。
2. 剪枝法剪枝：在搜索过程中，对某些结点进行剪枝，减少不必要的搜索，例如，在8-数码问题中，可以根据每个数字在未来的可能性进行剪枝。
3. 深度限制剪枝：在搜索过程中，设置搜索深度的限制，当搜索深度超过限制时直接返回，一般来说，深度限制应该在问题的解的最小深度和最大深度之间。
4. 估价函数剪枝：在搜索过程中，使用估价函数对当前结点进行估价，当估价值较大时直接返回。

例子：深度优先搜索迷宫

我们有一个迷宫，其中起点为 (0,0)，终点为 (n-1,n-1)。我们需要使用DFS算法找到一条从起点到终点的路径。

首先，我们需要定义一个二维数组来存储迷宫地图，其中0表示可以通过的点，1表示不能通过的点。接着，我们需要定义一个栈来存储当前搜索的路径。

在DFS算法执行过程中，我们首先将起点入栈，并将起点标记为已访问。然后，每次从栈顶取出一个点，并在上下左右四个方向上搜索下一个点。如果找到了终点，则DFS算法结束；否则，继续寻找下一个点。

// define the stack to store the path
stack<pair<int, int>> path;

// define the 2D array to store the maze
int maze[N][N];

// define the visited array to store the visited node
bool visited[N][N];

bool DFS(int x, int y) {
    // if we find the destination
    if (x == n - 1 && y == n - 1) {
        return true;
    }

// mark the current point as visited
visited[x][y] = true;

// push the current point into the stack
path.push({x, y});

// check the right point
if (y + 1 < n && !visited[x][y + 1] && !maze[x][y + 1]) {
    if (DFS(x, y + 1)) {
        return true;
    }
}

// check the down point
if (x + 1 < n &&!visited[x + 1][y] && !maze[x + 1][y]) {
if (DFS(x + 1, y)) {
return true;
}
}
// check the left point
if (y - 1 >= 0 && !visited[x][y - 1] && !maze[x][y - 1]) {
    if (DFS(x, y - 1)) {
        return true;
    }
}

// check the up point
if (x - 1 >= 0 && !visited[x - 1][y] && !maze[x - 1][y]) {
    if (DFS(x - 1, y)) {
        return true;
    }
}

// if we can't find the path, pop the current point from the stack
path.pop();
return false;

​

在这个例子中，我们使用栈来存储当前搜索的路径，并在找到终点时返回 true。如果找不到终点，则返回 false。如果找不到终点，这个点也会被从栈中弹出。

这是一个简单的DFS算法的实现，但是在实际应用中，它可能会搜索到非常多的点，导致算法效率低下。因此，我们需要使用剪枝技巧来优化DFS算法。