遍历图Vs遍历树

Question

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

Answer 1

树只是一种特殊类型的图，称为有向无循环图，因此yes...Breadth优先和深度优先遍历都在树上工作。

我可以详细解释广度优先遍历和深度优先遍历之间的区别，但我可能会弄错(我还不是一个很喜欢comp-sci的人)。

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

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

在谷歌上快速搜索一下(我不知道它是广度还是深度优先)就会找到this，它似乎很好地描述了BFS和DFS之间的区别。如果你想获得更深入的阅读，我也可以推荐Steve Skiena的The Algorithm Design Manual。

Answer 2

一个可以遍历一般图的函数对于遍历一棵树来说可能过于夸张了，因为在纯树中，您不必检查是否有循环。所以它是可行的，但更简单的东西也是如此。