图的环检测对bfs和dfs两种方法哪个更好

Question

老师，你好，环检测课上是讲了dfs的方式，那么我想问下，bfs去作环检测和dfs比起来，哪个效果更好:)

Answer 1

liuyubobobo 2020-01-06 00:49:00

效率一样好，都是 O(E + V) 的。

如果真要细扣，bfs 更好，因为 dfs 的递归过程有不断函数调用的开销。并且如果图特别特别大的话，有系统栈溢出的风险。但是，在大多数情形下，都是没有问题。一般在程序竞赛中，我习惯写 dfs，因为代码量小：）

继续加油！：）