图论中的深度优先搜索算法

题目描述：给定一个无向图，包含n个节点和m条边。请实现深度优先搜索算法，从指定起始节点开始遍历整个图，并输出节点的访问顺序。

解题过程：

1. 算法基础理解
   深度优先搜索采用"一条路走到黑"的策略。从起始节点开始，沿着一条路径不断深入，直到无法继续前进，然后回溯到上一个分叉点选择另一条路径。

2. 核心数据结构准备
   我们需要三个关键数据结构：

• 邻接表：存储图的连接关系
• 访问标记数组visited：记录每个节点是否被访问过
• 栈：用于实现回溯机制（递归调用栈或显式栈）

3. 具体实现步骤
   步骤1：初始化visited数组，所有元素设为false
   步骤2：创建空栈，将起始节点入栈
   步骤3：当栈不为空时循环执行：
   a. 弹出栈顶节点v
   b. 如果v未被访问：

   • 标记v为已访问
   • 输出或记录访问顺序
   • 将v的所有未访问邻接节点逆序入栈（保证访问顺序一致性）

4. 递归实现版本（更简洁）

def dfs_recursive(graph, v, visited):
    visited[v] = True
    print(f"访问节点 {v}")
    
    for neighbor in graph[v]:
        if not visited[neighbor]:
            dfs_recursive(graph, neighbor, visited)

5. 迭代实现版本（避免递归深度限制）

def dfs_iterative(graph, start):
    visited = [False] * len(graph)
    stack = [start]
    
    while stack:
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            print(f"访问节点 {v}")
            # 逆序入栈保证正序访问
            for neighbor in reversed(graph[v]):
                if not visited[neighbor]:
                    stack.append(neighbor)

6. 算法特性分析

• 时间复杂度：O(V+E)，其中V是节点数，E是边数
• 空间复杂度：O(V)，主要取决于递归深度或栈大小
• 能够探索图的连通分量
• 可用于检测环、路径查找等应用

7. 实际遍历示例
   以5个节点的图为例：0-1-2, 0-3, 3-4
   从节点0开始遍历，可能的访问顺序：0→1→2→3→4
   具体路径取决于邻接表的存储顺序