深度优先搜索 (Depth-First Search, DFS)

算法原理

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深地搜索树的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

算法步骤

1. 从起始节点开始，标记该节点为已访问
2. 访问该节点（例如打印节点值）
3. 对于当前节点的每个未访问过的邻接节点，递归地执行深度优先搜索
4. 如果当前节点没有未访问的邻接节点，则回溯到上一个节点
5. 重复步骤1-4直到所有节点都被访问

代码实现

import java.util.*;

public class DFSGraph {
    // 图的邻接表表示
    private Map> adjList;
    
    public DFSGraph() {
        adjList = new HashMap<>();
    }
    
    // 添加边
    public void addEdge(int v, int w) {
        adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(w);
    }
    
    // 深度优先搜索（递归实现）
    public void DFS(int startVertex) {
        Set visited = new HashSet<>();
        DFSUtil(startVertex, visited);
    }
    
    // DFS辅助函数
    private void DFSUtil(int vertex, Set visited) {
        // 标记当前节点为已访问并打印
        visited.add(vertex);
        System.out.print(vertex + " ");
        
        // 递归访问所有未访问的邻接节点
        List neighbors = adjList.getOrDefault(vertex, new ArrayList<>());
        for (Integer neighbor : neighbors) {
            if (!visited.contains(neighbor)) {
                DFSUtil(neighbor, visited);
            }
        }
    }
    
    // 深度优先搜索（迭代实现）
    public void DFSIterative(int startVertex) {
        Set visited = new HashSet<>();
        Stack stack = new Stack<>();
        
        stack.push(startVertex);
        
        while (!stack.isEmpty()) {
            int vertex = stack.pop();
            
            if (!visited.contains(vertex)) {
                visited.add(vertex);
                System.out.print(vertex + " ");
                
                // 将邻接节点压入栈中（逆序压入以保证正确的访问顺序）
                List neighbors = adjList.getOrDefault(vertex, new ArrayList<>());
                for (int i = neighbors.size() - 1; i >= 0; i--) {
                    int neighbor = neighbors.get(i);
                    if (!visited.contains(neighbor)) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }

    // 测试方法
    public static void main(String[] args) {
        DFSGraph graph = new DFSGraph();
        
        // 构建图
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);
        
        System.out.println("递归DFS遍历结果 (从节点2开始):");
        graph.DFS(2);
        System.out.println();
        
        System.out.println("迭代DFS遍历结果 (从节点2开始):");
        graph.DFSIterative(2);
        System.out.println();
    }
}

应用场景

• 图的连通性检测：判断图中任意两点是否连通
• 路径查找：寻找从起点到终点的路径
• 拓扑排序：对有向无环图进行排序
• 强连通分量：寻找图中的强连通分量
• 迷宫求解：寻找从入口到出口的路径

优缺点