如何在Python中高效实现无重复节点的递归DFS？

你的问题核心在于用列表path做成员检查——列表的in操作是线性时间复杂度O(n)，当图的节点数量较多时，效率会急剧下降。解决思路是用集合（set）来存储已访问的节点，因为集合的成员检查是常数时间O(1)，能大幅提升效率。

另外，你的代码还有一个隐藏坑：Python中可变默认参数（比如path=[]）会在函数定义时初始化，多次调用函数时会复用同一个列表，可能导致意外的结果。我们可以一起修复这两个问题。

优化后的递归DFS实现 #

def dfs_recursive(graph, vertex, visited=None, path=None):
    # 初始化默认参数，避免可变默认参数的陷阱
    if visited is None:
        visited = set()
    if path is None:
        path = []
    
    # 标记当前节点为已访问
    visited.add(vertex)
    path.append(vertex)
    
    # 遍历所有邻居节点
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, path)
    
    return path

adjacency_matrix = {"s": ["a", "c", "d"], "c": ["e", "b"], "b": ["d"], "d": ["c"], "e": ["s"], "a": []}
print(dfs_recursive(adjacency_matrix, "s"))

代码解释 #

1. 使用集合存储已访问节点：visited是一个集合，用来快速判断节点是否已经被访问过，替代了原来用path做检查的低效方式。
2. 修复可变默认参数问题：把visited和path的默认值设为None，在函数内部初始化，确保每次调用函数时都会创建新的集合和列表，避免复用旧数据。
3. 递归逻辑：访问当前节点后，遍历所有邻居，若邻居未被访问过，则递归调用DFS，共享同一个visited集合和path列表，保证状态一致。

运行这段代码，会输出你预期的结果：

['s', 'a', 'c', 'e', 'b', 'd']

额外说明 #

如果不需要保留完整路径，只需要输出访问顺序，还可以把path作为闭包变量减少参数传递，但上面的实现已经足够清晰高效，适合大多数场景。

内容的提问来源于stack exchange，提问作者Simd