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

难度 / Difficulty: 中等 (Medium)
分类 / Category: 图遍历 (Graph Traversal)
时间复杂度 / Time Complexity: O(V + E)
空间复杂度 / Space Complexity: O(V)

📖 算法简介 / Introduction

深度优先搜索是一种Graph/树遍历算法，沿着一条路径走到底，然后回溯探索其他路径。

DFS is a graph/tree traversal algorithm that explores as far as possible along each branch before backtracking.

💡 算法原理 / Principle

从起点开始，尽可能深地访问节点，直到没有未访问的邻居，然后回溯。

Start from the source, visit nodes as deep as possible, until no unvisited neighbors, then backtrack.

📝 代码实现 / Implementation

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

✨ 示例 / Example

在Graph {‘A’: [‘B’, ‘C’], ‘B’: [‘D’, ‘E’], ‘C’: [‘F’], ‘D’: [], ‘E’: [‘F’], ‘F’: []} 中从A开始遍历。

Traversing graph from node A in {‘A’: [‘B’, ‘C’], ‘B’: [‘D’, ‘E’], ‘C’: [‘F’], ‘D’: [], ‘E’: [‘F’], ‘F’: []}.

🎯 适用场景 / Scenarios

迷宫求解, 拓扑排序, 连通分量检测

Maze solving, Topological sorting, Connected components

🔄 扩展阅读 / Further Reading

• 建议在 LeetCode 或 HackerRank 上刷相关题目
• 尝试自己实现非递归版本
• 对比其他同类型算法的性能差异