我应该在树遍历中使用BFS、DFS还是中序遍历、后序遍历、前序遍历？

Question

这个问题对于专家来说可能很简单，但对于像我这样的初学者来说非常重要。我的问题是是否有一些树遍历问题只能通过BFS、DFS而不是in-order、pre-order等方法来解决。换句话说，每当我看到一个树的问题时，我应该只考虑这3种树遍历方法吗？还是也应该考虑BFS和DFS呢？

- Programmer

Answer 1

先序遍历、中序遍历和后序遍历是三种不同的深度优先搜索方式。因此，问题并不在于使用深度优先搜索还是这三种方法之一。如果您正在使用其中一种遍历方法，则您就是在使用深度优先搜索。

至于是否有BFS比DFS更可取的情况：是的，有。例如，在无权图中查找两个节点之间的最短路径时，可以使用BFS，因为BFS找到的第一条路径恰好是边数最少的路径。但对于DFS来说则不是这样。

- sepp2k

---

有没有类似于 BFS 的树遍历方法？ - Programmer

需要注意的是，遍历和搜索之间存在细微的差别。遍历会遍历所有节点，而搜索会在找到节点时停止。 - modest

例如，要在无权图中找到两个节点之间的最短路径，可以使用 BFS，因为 BFS 找到的第一条路径恰好是具有最少边数的路径。我相信你的意思是 BFS 有可能比 DFS 更早地找到最短路径，但并非总是如此。对吧？ - M Sach

@MSach 我的意思是，如果你在一个无权图中从节点A开始使用BFS，并在找到节点B时停止，那么这将给你最短的路径。如果你用DFS做同样的事情，你会得到一条任意的路径，可能仅仅是巧合下的最短路径，而你没有办法知道它是否是最短的。要想深度优先地找到最短路径，唯一的方法就是进行完整的遍历，找到从A到B的所有路径，然后选择最短的路径。 - sepp2k

@sepp2k 我只是在考虑节点A处于第一级的情况。节点B，C，D，E，F处于第二级，在这里你可以通过A>B>C>D>E或A>F>E到达E，我们也需要找到到达E的所有路径吗？ - M Sach

Answer 2

一个明显的例子是，当你遇到一个无限高（或者至少非常高）的树时，DFS就不再适用了，必须使用BFS。

- Jörg W Mittag