最短时间学会基于C++实现DFS深度优先搜索

最短时间学会基于C++实现DFS深度优先搜索攻略

什么是DFS深度优先搜索

DFS即深度优先搜索，是一种基于搜索算法的遍历和检索树或图数据结构的算法。DFS算法采用深度优先策略，从根结点出发访问所有可达结点，直到叶子节点。在访问某个结点时，先访问该结点的第一个未访问的相邻节点，然后递归的访问其非相邻节点。其搜索的核心思想是根据某个搜索方向向前搜索到底，直至无法继续下去时就回到上一个结点重新选择另一片区域搜索，直至所有结点都被访问。

实现DFS深度优先搜索

方式一：递归实现DFS深度优先搜索

递归实现DFS深度优先搜索比较简单，只需要实现以下三个步骤：

1. 判断当前节点是否已经被访问过，如果访问过，返回。
2. 将当前节点标记为已访问。
3. 对当前节点的所有未被访问过的临界节点进行访问，递归重复以上步骤。

void dfs(int cur, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[cur] = true;
    for (int i = 0; i < graph[cur].size(); i++) {
        int neighbor = graph[cur][i];
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

方式二：栈实现DFS深度优先搜索

使用栈来实现DFS深度优先搜索的方法，具备更好的可读性和可维护性。由于需要遍历到所有未访问的节点，因此不能直接用栈进行遍历，需要将根节点压入栈内，然后使用while循环进行遍历，直到栈为空。

void dfs(int start, vector<vector<int>>& graph, vector<bool>& visited) {
    stack<int> s;
    s.push(start);
    while (!s.empty()) {
        int cur = s.top();
        s.pop();
        if (visited[cur]) continue;
        visited[cur] = true;
        for (int i = graph[cur].size() - 1; i >= 0; i--) {
            int neighbor = graph[cur][i];
            if (!visited[neighbor]) {
                s.push(neighbor);
            }
        }
    }
}

示例1：图的遍历

例如，我们要遍历一个图，对该图进行DFS深度优先搜索，可以使用以下代码：

int main() {
    vector<vector<int>> graph(5);
    graph[0].push_back(1);
    graph[1].push_back(2);
    graph[2].push_back(3);
    graph[3].push_back(4);
    graph[4].push_back(1);

    vector<bool> visited(5, false);
    dfs(0, graph, visited);

    return 0;
}

以上代码中，我们以图中的0号节点为起始节点，进行深度优先遍历。

示例2：迷宫的搜索

以下代码提供一个方格迷宫搜索的示例，使用DFS深度优先搜索解决，其中，我们使用了递归。

int maze[5][5] = {
    { 0, 0, 0, 0, 1 },
    { 0, 1, 0, 1, 0 },
    { 0, 0, 0, 1, 0 },
    { 1, 1, 0, 0, 0 },
    { 0, 0, 1, 0, 0 }
};

bool visited[5][5];
int dstX = 4, dstY = 4;

bool dfs(int curX, int curY) {
    if (curX < 0 || curY < 0 || curX >= 5 || curY >= 5 || visited[curX][curY] || maze[curX][curY] == 1) {
        return false;
    }
    if (curX == dstX && curY == dstY) {
        return true;
    }
    visited[curX][curY] = true;
    if (dfs(curX-1, curY) || dfs(curX+1, curY) || dfs(curX, curY-1) || dfs(curX, curY+1)) {
        return true;
    }
    visited[curX][curY] = false;
    return false;
}

总结

以上是两种实现DFS深度优先搜索的方法及其示例解决方案。简单的递归实现可以快速实现，但是在处理效率相对较低的情况下会出现栈空间不足的问题，此时栈毕竟是有限大小的，如果栈深度过大会导致程序崩溃。栈实现的方法则可以避免这个问题。