首页 文章

Python中的递归深度优先搜索

提问于
浏览 次
1

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

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

它表示达到了最大递归深度 . 我该如何解决？

python recursion graph depth-first-search

2 回答

  • 0

    我可以看到这种行为的主要原因是每次递归调用时重新初始化 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

    之后，改变算法似乎是正确的 . 但问题mentioned by Esdes仍然存在 . 如果要正确遍历大小为 n 的图形，则需要执行 sys.setrecursionlimit(n + 10) . 10 表示 dfs_tree 之外的嵌套函数调用的最大数量，包括隐藏的初始调用 . 如果需要，你应该增加它 .

    但这不是最终的解决方案 . Python解释器对堆栈内存本身有一些限制，这取决于操作系统和某些设置 . 因此，如果您将 recursionlimit 增加到某个阈值以上，那么当解释器's memory limit is exceeded. I don' t准确记住此阈值的近似值时，您将开始出现"segmentation fault"错误，但它看起来大约是3000次调用 . 我现在没有翻译检查 .

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

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

    回复于
  • -1

    要修复此错误，只需增加默认的递归深度限制（默认情况下为1000）：

    sys.setrecursionlimit(2000)
    回复于

相关问题