老师您好，关于实际生产环境中DFS实现的问题

Question

我用《算法四》中的测试数据（一百万个结点，七百万条边）去测试我的DFS递归实现（C++），发现很容易就栈溢出了，加大栈容量到16M，最多也就遍历两三万个结点就栈溢出。所以想请教一下，实际生产环境中或者成熟的软件产品中，它们的图的DFS实现是不是都是使用迭代（配合后入先出栈）方式实现？

Answer 1

liuyubobobo 2023-01-07 11:43:30

如果数据量确实到达当前环境的内存无法承受的程度，需要把递归算法改成非递归算法。所有的递归算法都一定能改成非递归算法，方法是手动设置一个栈模拟系统栈的运行。

另外一个解决方案是使用 BFS。

另外，对于现代一般家用计算机来说，100 万节点的递归应该不成问题，通常是编译或者运行环境限制了对系统内存的使用。你可以设置你的编译运行环境的相关参数。比如可以查询类似这样的问题：https://stackoverflow.com/questions/54821412/how-to-increase-stack-size-when-compiling-a-c-program-using-mingw-compiler

继续加油！：）

• 提问者 qq_不睡觉的怪叔叔_0 #1

  寻找桥的Tarjan算法怎么改成非递归的方式呢？想了很久不知道怎么写，请问有相关的示例代码或者资料书籍吗？

• liuyubobobo 回复 提问者 qq_不睡觉的怪叔叔_0 #2

  所有的递归调用在计算机内部都是顺次执行的指令，计算机执行递归的方式是：在计算机内部有一个系统栈，递归的过程是将此次递归函数运行的相关信息压入系统栈，然后执行新的递归调用，新的递归调用执行完毕后，在系统中取出压入系统站的函数信息，执行上层的递归调用。我们永远可以使用手动设置一个栈的方式来手动执行系统栈的功能，将一切递归转为非递归。这种转换和具体算法无关。可以参考类似这样的文章：https://www.less-bug.com/posts/simulation-of-stack/