深度优先遍历应用案例

深度优先遍历（Depth-First Traversal）是一种常见的图或树的遍历算法。它沿着一个分支一直遍历到底，然后再退回上一层继续探索其他分支。这种遍历方式非常适合解决诸如迷宫求解、子集生成等问题。

1. 迷宫求解

假设有一个迷宫（可以用二维数组表示），其中 0 表示可以通过的路径，1 表示障碍物。目标是找到从起点到终点的一条通路。使用深度优先遍历可以帮助我们实现这一目的。

def dfs(maze, start, end):
    stack = [start]
    visited = set()
    
    while stack:
        current = stack.pop()
        
        if current == end:
            return True
        
        if current in visited:
            continue
        
        visited.add(current)
        
        x, y = current
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:  # 右、下、左、上四个方向
            next_x, next_y = x + dx, y + dy
            
            if 0 <= next_x < len(maze) and 0 <= next_y < len(maze[0]) and maze[next_x][next_y] == 0:
                stack.append((next_x, next_y))
    
    return False

# 示例迷宫
maze = [
    [0, 1, 0, 0],
    [0, 1, 0, 1],
    [0, 0, 0, 0],
    [1, 1, 1, 0]
]

start = (0, 0)
end = (3, 3)

result = dfs(maze, start, end)
print("是否存在通路:", result)

2. 子集生成

深度优先遍历也可以用于生成所有可能的子集。假设我们有一个包含若干元素的集合，目标是找到所有的子集。

def generate_subsets(nums):
    def dfs(index, path):
        # 将当前路径添加到结果集中
        result.append(path)
        
        for i in range(index, len(nums)):
            # 选择当前数字加入子集
            dfs(i + 1, path + [nums[i]])
    
    result = []
    nums.sort()  # 排序是为了保证输出的子集有序
    dfs(0, [])
    return result

# 示例数组
nums = [1, 2, 3]

subsets = generate_subsets(nums)
print("所有可能的子集:", subsets)

3. 检测图中环路

深度优先遍历不仅可以用来遍历图，还可以检测图中的环路。通过标记访问过的节点并记录它们的状态（未访问、正在访问、已访问），可以有效地发现环。

def detect_cycle(graph, start):
    def dfs(node):
        visited[node] = 'visiting'
        
        for neighbor in graph[node]:
            if visited[neighbor] == 'unvisited':
                if dfs(neighbor):
                    return True
            elif visited[neighbor] == 'visiting':
                return True
        
        visited[node] = 'visited'
        return False
    
    n = len(graph)
    visited = ['unvisited'] * n

    for i in range(n):
        if visited[i] == 'unvisited' and dfs(i):
            return True
    return False

# 示例图结构
graph = {
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: []
}

has_cycle = detect_cycle(graph, 0)
print("是否存在环路:", has_cycle)

通过上述案例，可以看到深度优先遍历在实际问题中有着广泛的应用。无论是解决迷宫路径问题、生成子集还是检测图中的环路，它都能发挥重要作用。