使用 Python 和 DFS 算法的递归深度问题

Question

DFS 算法已经在处理小测试用例，但是当我运行它处理大量样本时它抛出 "RuntimeError: maximum recursion depth exceeded"，所以我包含 sys.setrecursionlimit(10 ** 6) 并且系统抛出这个消息："python.exe stopped working" 和 PyCharm 抛出消息："Process finished with exit code -1073741571 (0xC00000FD)"。您可以下载 sample.

的 zip 文件

代码：

import sys
import threading

threading.stack_size(67108864)
sys.setrecursionlimit(10 ** 6)


def get_input(filename):
    graph_map = {}

    for line in open(filename, 'r').readlines():
        values = [int(val) for val in line.split()]
        key1 = values.pop(0)
        key2 = values.pop(0)

        if not key1 in graph_map:
            graph_map[key1] = []

        if not key2 in graph_map:
            graph_map[key2] = []

        graph_map[key1].extend([key2])

    return graph_map


def DFS(graph_map, start):
    global visited

    visited[start-1] = True

    for child in graph_map[start]:
        if visited[child-1] is False:
            DFS(graph_map, child)


def DFS_Loop(graph_map):
    global visited

    i = len(graph_map)  # max(graph_map.keys())
    for i in reversed(range(1, i+1)):
        if visited[i-1] is False:
            DFS(graph_map, i)


graph_map = get_input("SCC.txt")
visited = [False]*len(graph_map)  # size of the graph
DFS_Loop(graph_map)

有没有办法在不取消递归的情况下实现这一点？

提前致谢。

Answer 1

您需要更改系统堆栈限制。在 linux 你可以这样做：

ulimit -s 1000000（对于 windows 检查 here）

然后我运行你的程序，正常退出了。

Answer 2

Python 的一个很酷的事情是迭代器只是一种普通的数据类型。尽管人们通常使用 for 循环和理解来迭代，但如果方便的话，没有什么可以阻止您手动进行迭代。它可能很方便的原因之一是通过用显式堆栈替换深度递归来避免深度递归。

虽然这确实“消除了递归”，但并没有使程序明显复杂化，而且递归结构仍然很明显。 Python 根本无法优雅地递归，因此这种转换通常很有用。

写的时候

for child in graph_map[start]:
    ...

您正在执行与以下内容非常相似的操作：

it = iter(graph_map[start])
try:
  child = next(it)
  ...
except StopIteration:
  pass

[见注释 1]

iter 函数 returns 集合（或其他可迭代对象，例如推导式、生成器或范围）的迭代器。 next 方法 returns 下一个值，并推进迭代器；如果没有下一个值，则会引发 StopIteration 异常。

DFS 函数只是针对其参数的每个未访问子项递归地调用自身。我们可以使用一堆迭代器精确地模拟该行为。我们不是递归地调用一个节点，而是将一个迭代器推送到节点的子节点到迭代器堆栈上。当堆栈顶部的迭代器终止时，我们会将其弹出堆栈。

def DFS(graph_map):
  visited = [False] * len(graph_map)
  # By initializing the stack with a range iterator, we do
  # the equivalent of DFS_Loop.
  # In Python2, you should use xrange instead of range
  stack = [iter(range(len(graph_map), 0, -1))]
  while stack:
    try:
      child = next(stack[-1])
      if not visited[child - 1]:
        visited[child - 1] = True
        # Do whatever you want to do in the visit
        stack.append(iter(graph_map[child]))
    except StopIteration:
      stack.pop()

应用于OP中提供的文件中示例数据的上述函数最多使用了62794个堆栈槽。在我的 Linux 笔记本电脑上，读入数据大约需要 3 秒；我没有准确计时。

同样有趣的是，只需将堆栈更改为队列，即可将上面的内容更改为广度优先搜索。对于深度搜索，堆栈必须是一个迭代器堆栈（或等价物，在不那么简单的语言中）；对于广度搜索优先，队列可能是一个迭代器队列，但它也可以使用值队列。

备注

实际虚拟机使用定义的迭代器协议，在Python2和Python3之间略有不同。在这两个版本中，容器（或其他可迭代）对象都有一个名为 __iter__ 的成员函数，其中 returns 是一个新创建的迭代器对象。迭代器对象在 Python2 中有一个名为 next 的方法，在 Python3 中有一个名为 __next__ 的方法，它 returns 当前值并推进迭代器。从 2.6 开始，您可以使用 iter 和 next 全局函数来避免担心这些细节，这就是我在这里所做的。

使用 Python 和 DFS 算法的递归深度问题

Recursion depth issue using Python with DFS algorithm

algorithm

recursion

python-3.x

备注