深度优先搜索

深度优先搜索（DFS）是一种图遍历算法，沿着一条路径尽可能深地探索。

概述

深度优先搜索优先访问子节点，直到到达叶子节点，然后回溯。

算法步骤

1. 访问起始节点
2. 递归访问未访问的相邻节点
3. 回溯到上一个节点继续探索

实现（递归）

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

# 示例图
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("DFS 遍历结果:")
dfs(graph, 'A')  # A B D E F C

实现（迭代）

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node, end=' ')
            # 逆序添加以保持顺序
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return visited

print("\nDFS 迭代遍历结果:")
dfs_iterative(graph, 'A')  # A C F E B D

复杂度分析

复杂度	值
时间复杂度	O(V + E)
空间复杂度	O(V)

应用场景

图遍历

# 检测图中是否存在路径
def has_path(graph, start, end, visited=None):
    if visited is None:
        visited = set()
    
    if start == end:
        return True
    
    visited.add(start)
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            if has_path(graph, neighbor, end, visited):
                return True
    
    return False

# 示例
print("\nA 到 F 是否有路径:", has_path(graph, 'A', 'F'))  # True

拓扑排序

# 基于 DFS 的拓扑排序
def topological_sort(graph):
    visited = set()
    stack = []
    
    def dfs(node):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(node)
    
    for node in graph:
        if node not in visited:
            dfs(node)
    
    return stack[::-1]

# 有向无环图
dag = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['E'],
    'D': ['F'],
    'E': ['F'],
    'F': []
}

print("\n拓扑排序结果:", topological_sort(dag))  # ['A', 'C', 'B', 'E', 'D', 'F']

连通分量

# 计算图中的连通分量
def count_connected_components(graph):
    visited = set()
    count = 0
    
    for node in graph:
        if node not in visited:
            dfs(graph, node, visited)
            count += 1
    
    return count

# 示例
graph_with_components = {
    'A': ['B', 'C'],
    'B': ['A'],
    'C': ['A'],
    'D': ['E'],
    'E': ['D'],
    'F': []
}

print("\n连通分量数量:", count_connected_components(graph_with_components))  # 3

变体

深度优先搜索（前序遍历）

# 树的前序遍历
def preorder_traversal(root):
    if root is None:
        return
    
    print(root.value, end=' ')
    preorder_traversal(root.left)
    preorder_traversal(root.right)

深度优先搜索（中序遍历）

# 树的中序遍历
def inorder_traversal(root):
    if root is None:
        return
    
    inorder_traversal(root.left)
    print(root.value, end=' ')
    inorder_traversal(root.right)

深度优先搜索（后序遍历）

# 树的后序遍历
def postorder_traversal(root):
    if root is None:
        return
    
    postorder_traversal(root.left)
    postorder_traversal(root.right)
    print(root.value, end=' ')

与 BFS 的对比

特性	DFS	BFS
数据结构	栈	队列
空间复杂度	O(V)	O(V)
最短路径	不保证	保证
适用场景	连通性检测、拓扑排序	最短路径、层序遍历