tree - 遍历图与遍历树

Question

遍历图的函数是否同样适用于遍历树？

Answer 1

好吧，树只是一种特殊类型的图，称为有向无环图，所以是的……广度优先和深度优先遍历都适用于树。

我可以写出关于广度和深度优先遍历之间差异的详细解释，但我可能会弄错（我还不是一个沉重的 comp-sci 人）。

可以这么说，宽度优先遍历和深度优先遍历之间的唯一区别是处理顶点的顺序。广度优先，您可以将其视为将顶点添加到“待处理”队列。深度优先，您可以将其视为将顶点添加到“待处理”堆栈中。当需要处理顶点时（在它们被添加到各自的数据结构中之后），您可以出列或弹出堆栈以获取下一个要处理的顶点。深度优先遍历的聪明版本使用递归来处理顶点，而不是将它们添加到堆栈中。

我不知道这是否有帮助...

一个快速的谷歌搜索（我不知道它是首先是广度还是深度）发现这似乎很好地描述了 BFS 和 DFS 之间的差异。如果您想更深入地阅读，我还可以推荐 Steve Skiena 的算法设计手册。

Answer 2

可以遍历一般图的函数对于遍历树来说可能是多余的，因为在纯树中您不必检查循环。所以它会起作用，但更简单的东西也会起作用。