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

来源：3-4 实现图的深度优先遍历

qq_不睡觉的怪叔叔_0

2023-01-07

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

写回答

1回答

liuyubobobo

2023-01-07

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

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

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

继续加油！：）

liuyubobobo

qq_不睡觉的怪叔叔_0

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

2023-01-11

共2条回复

玩转算法系列--图论精讲（Java版）

30+小时系统学习，bobo带你克服被图论支配的恐惧

1591 学习 · 324 问题

查看课程

相似问题

关于寻找割点

回答 1

5-2 图的BFS的JS实现

回答 1

邻接表和树

回答 1

感谢bobo老师，同时求建议

回答 1

关于有向图的数据结构（实现）

回答 1

打开慕课网App查看更多内容