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

Question

DFS 算法已经在处理小型测试用例，但是当我使用大量样本运行它时，它会抛出“RuntimeError：超出最大递归深度”，因此我包含在内sys.setrecursionlimit(10 ** 6)并且系统抛出此消息：“python.exe 停止工作”和 PyCharm抛出消息：“进程已完成，退出代码为 -1073741571 (0xC00000FD)”。您可以下载示例的 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

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

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

当你写

for child in graph_map[start]:
    ...

您正在做与以下非常相似的事情：

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

[见注1]

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

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 秒；我没有准确计时。

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

笔记

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