DFS算法已经在处理小的测试用例，但当我用一个巨大的样本运行它时，它会抛出"RuntimeError:超过了最大递归深度"，所以我包含了sys.setrecursionlimit(10 ** 6)，系统会抛出这样的消息："python.exe停止工作"，PyCharm会抛出消息："进程完成，退出代码为-10073741571（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)
有没有什么方法可以在不取消递归的情况下实现这一点？
提前谢谢。
Python最酷的一点是迭代器只是一种普通的数据类型。尽管通常使用循环和理解来迭代，但如果方便的话，没有什么可以阻止您手动进行迭代。它可能很方便的一个原因是通过用显式堆栈替换它来避免深度递归。
虽然这确实"；去掉递归"；，它不会使程序显著复杂化，并且递归结构仍然很明显。Python根本不会优雅地递归，所以这种转换通常很有用。
当你写
for child in graph_map[start]:
...
你正在做与以下内容非常相似的事情：
it = iter(graph_map[start])
try:
child = next(it)
...
except StopIteration:
pass
[参见注释1]
iter函数返回集合（或其他可迭代对象，如理解、生成器或范围）的迭代器。next方法返回下一个值，并推进迭代器；如果没有下一个值，则引发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__的成员函数，它返回一个新创建的迭代器对象。迭代器对象在Python 2中有一个名为next的方法，在Python 3中有一个称为__next__的方法，它返回当前值并推进迭代器。从2.6开始，您可以使用iter和next全局函数来避免担心这些细节，这就是我在这里所做的
您需要更改系统堆栈限制。在linux上，你可以这样做：
ulimit -s 1000000（此处查看窗口）
然后我运行了你的程序，它正常退出。