深度优先搜索

深度优先搜索（Depth-First Search，简称 DFS）是一种用于遍历或搜索树/图的算法。
它的基本思想是从一个顶点开始，尽可能深地搜索树的分支。

基本概念

DFS 的工作原理类似于走迷宫：

从起点开始，选择一个方向前进
一直走到无法继续为止
返回到上一个还有其他出路的位置
选择另一个方向继续探索
重复以上步骤直到找到目标或探索完整个迷宫

实现方式

DFS 主要有两种实现方式：

递归
栈

递归实现

cpp
java
python

void dfs(int node, set<int>& visited, vector<vector<int>>& graph) {
    // 访问当前节点
    visited.insert(node);
    cout << "访问节点: " << node << endl;
    
    // 遍历所有相邻节点
    for (int neighbor : graph[node]) {
        if (visited.find(neighbor) == visited.end()) {
            dfs(neighbor, visited, graph);
        }
    }
}

public void dfs(int node, Set<Integer> visited, List<List<Integer>> graph) {
    // 访问当前节点
    visited.add(node);
    System.out.println("访问节点: " + node);
    
    // 遍历所有相邻节点
    for (int neighbor : graph.get(node)) {
        if (!visited.contains(neighbor)) {
            dfs(neighbor, visited, graph);
        }
    }
}

def dfs(node, visited=None):
    if visited is None:
        visited = set()
    # 访问当前节点
    visited.add(node)
    print(f"访问节点: {node}")
    # 遍历所有相邻节点
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, visited)

栈实现

void dfs_stack(int start, vector<vector<int>>& graph) {
    stack<int> s;
    set<int> visited;
    s.push(start);
    
    while (!s.empty()) {
        int node = s.top();
        s.pop();
        
        if (visited.find(node) == visited.end()) {
            visited.insert(node);
            cout << "访问节点: " << node << endl;
            
            for (int neighbor : graph[node]) {
                if (visited.find(neighbor) == visited.end()) {
                    s.push(neighbor);
                }
            }
        }
    }
}

java
python

public void dfs_stack(int start, List<List<Integer>> graph) {
    Stack<Integer> stack = new Stack<>();
    Set<Integer> visited = new HashSet<>();
    stack.push(start);
    
    while (!stack.isEmpty()) {
        int node = stack.pop();
        if (!visited.contains(node)) {
            visited.add(node);
            System.out.println("访问节点: " + node);
            
            for (int neighbor : graph.get(node)) {
                if (!visited.contains(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }
}

def dfs(graph, start):
    stack = [start]
    visited = set()
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(f"访问节点: {node}")
            stack.extend(graph[node])

应用场景

DFS 在很多实际问题中都有应用：

寻找图中的连通分量
拓扑排序
解决迷宫问题
查找图中的环
生成树的所有路径

示例：解决迷宫问题

cpp
java
python

vector<pair<int, int>> solve_maze(vector<vector<int>>& maze, pair<int, int> start, pair<int, int> end) {
    vector<pair<int, int>> directions = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
    
    auto is_valid = [&](int x, int y) {
        return x >= 0 && x < maze.size() && y >= 0 && y < maze[0].size() && maze[x][y] == 0;
    };
    
    auto dfs = [&](auto& self, int x, int y, vector<pair<int, int>> path) -> vector<pair<int, int>> {
        if (make_pair(x, y) == end) return path;
        
        for (auto [dx, dy] : directions) {
            int new_x = x + dx, new_y = y + dy;
            if (is_valid(new_x, new_y)) {
                bool in_path = false;
                for (auto& p : path) {
                    if (p.first == new_x && p.second == new_y) {
                        in_path = true;
                        break;
                    }
                }
                if (!in_path) {
                    path.push_back({new_x, new_y});
                    auto result = self(self, new_x, new_y, path);
                    if (!result.empty()) return result;
                    path.pop_back();
                }
            }
        }
        return vector<pair<int, int>>();
    };
    
    return dfs(dfs, start.first, start.second, {start});
}

public class Point {
    int x, y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public List<Point> solveMaze(int[][] maze, Point start, Point end) {
    int[][] directions = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    
    boolean isValid(int x, int y) {
        return x >= 0 && x < maze.length && y >= 0 && y < maze[0].length && maze[x][y] == 0;
    }
    
    List<Point> dfs(int x, int y, List<Point> path) {
        if (x == end.x && y == end.y) {
            return new ArrayList<>(path);
        }
        
        for (int[] dir : directions) {
            int newX = x + dir[0], newY = y + dir[1];
            Point newPoint = new Point(newX, newY);
            
            if (isValid(newX, newY) && !path.contains(newPoint)) {
                path.add(newPoint);
                List<Point> result = dfs(newX, newY, path);
                if (result != null) {
                    return result;
                }
                path.remove(path.size() - 1);
            }
        }
        return null;
    }
    
    List<Point> path = new ArrayList<>();
    path.add(start);
    return dfs(start.x, start.y, path);
}

def solve_maze(maze, start, end):
    def is_valid(x, y):
        return 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0
    def dfs(x, y, path):
        if (x, y) == end:
            return path
        # 四个方向：上、右、下、左
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        for dx, dy in directions:
            new_x, new_y = x + dx, y + dy
            if is_valid(new_x, new_y) and (new_x, new_y) not in path:
                result = dfs(new_x, new_y, path + [(new_x, new_y)])
                if result:
                    return result
        return None
    return dfs(start[0], start[1], [start])