深度优先遍历的优势？
来源：5-1 从树的广度优先遍历，到图的广度优先遍历
慕斯卡8072790
2021-09-24
图论中所有深度优先遍历DFS的算法 都可以用广度优先遍历BFS实现，并且时间复杂度都是 O(V+E)
广度优先遍历BFS有一个重要的性质是可得到无权图的最短路径
那么深度优先遍历DFS的优势是什么？是不是图论的无权图路径搜索问题可以无脑直接使用广度优先遍历BFS，而不用考虑深度优先遍历DFS。
写回答
1回答
-
对于以面试为目的的图论问题，你要是觉得 BFS 更顺手的话，无脑使用 BFS 基本没有问题。
不过有意思的是，我个人是认为 DFS 更顺手的。因为代码量更小。
==========
如果你一定要问 DFS 的“独特优势的话”，是有的，这个优势叫 DFS tree，他有一些特殊的应用。
在这个课程中，介绍“桥”和“割点”的算法，就是 DFS tree 最典型的应用；
介绍拓扑排序的时候，拓扑排序的一种算法的实现（不适用统计入度的方式），是 DFS tree 的应用；
SCC 的一种实现（Tarjan 算法，这个课程没有介绍），也是 DFS Tree 的应用。
但是，这些算法在面试中近乎都不可能碰到。拓扑排序是面试可能考的内容，但是使用统计入度的方式实现其实更容易且直观。
如果对 DFS Tree 感兴趣，这里是一个挺好的 tutorial：https://codeforces.com/blog/entry/68138
继续加油！：）
00
相似问题
图深度优先遍历JS实现
回答 1
回溯
回答 1