Python 中的递归深度优先搜索

Question

所以我一直在尝试在python中实现深度优先搜索递归。在我的程序中，我的目标是 return 父数组。（图中顶点的父级）

def dfs_tree(graph, start):
    a_list = graph.adjacency_list
    parent = [None]*len(a_list)
    state = [False]*len(a_list)
    state[start] = True

    for item in a_list[start]:
        if state[item[0]] == False:    
            parent[item[0]] = start
            dfs_tree(graph, item[0])
    state[start] = True

    return parent

表示已达到最大递归深度。我该如何解决这个问题？

Answer 1

要修复此错误，只需像这样增加默认递归深度限制（默认为 1000）：

sys.setrecursionlimit(2000)

Answer 2

我所看到的这种行为的主要原因是在每次递归调用时重新初始化 state（和 parent）数组。每次遍历只需初始化一次。常用的方法是将这些数组添加到函数参数列表中，用 None 初始化它们，并在第一次调用时用列表替换：

def dfs_tree(graph, start, parent=None, state=None):
    a_list = graph.adjacency_list
    if parent is None:
        parent = [None]*len(a_list)
    if state is None:
        state = [False]*len(a_list)
    state[start] = True

    for item in a_list[start]:
        if state[item[0]] == False:    
            parent[item[0]] = start
            dfs_tree(graph, item[0], parent, state)
    state[start] = True

    return parent

改算法后似乎是正确的。但是问题依然存在。如果你想正确遍历大小为 n 的图，你需要做 sys.setrecursionlimit(n + 10)。 10 表示 dfs_tree 之外的最大嵌套函数调用数，包括隐藏的初始调用。如果需要，您应该增加它。

但这不是最终的解决方案。 Python 解释器对堆栈内存本身有一些限制，这取决于 OS 和一些设置。因此，如果您将 recursionlimit 增加到某个阈值以上，当超出解释器的内存限制时，您将开始收到 "segmentation fault" 错误。我不记得这个阈值的确切近似值，但它看起来大约是 3000 次调用。我现在没有翻译可以检查。

在这种情况下，您可能需要考虑使用堆栈将算法重新实现为非递归版本，或者尝试更改 python 解释器的堆栈内存限制。

P.S. 您可能需要将 if state[item[0]] == False: 更改为 if not state[item[0]]:。比较布尔值通常被认为是一种不好的做法。

Python 中的递归深度优先搜索

Recursive Depth First Search in Python

python

recursion

graph

depth-first-search