algorithm - 这些情况下的 BFS 与 DFS？

Question

我无法决定在这两种情况下是使用 bfs 还是 dfs

情况 1:该图是高度为 40 且到任何叶节点的最小深度为 38 的不平衡无向边加权树。找到从根到任何叶的最小边成本的最佳算法是什么

情况 2:该图是一个最大堆，哪种算法最适合在堆的每一层中找到最大键值。

对于情况 1，我考虑的是 DFS，因为您不必遍历所有分支来找到最小的分支，第二个分支比您停止的比较大。

对于情况 2，我正在考虑 BFS，因为 BFS 一次从每个级别获取所有节点，并且更适合比较..

有什么建议吗？

Answer 1

我假设在这两种情况下，您只有一个指向树/堆根的指针。

无论使用 BFS 还是 DFS，这两种情况的最坏时间复杂度都是 O(n)，其中 n 是节点数。因此，您可能想出的任何优化都将是“平均”优化。

由于您给出的确切原因，对于情况 1，DFS 可能比 BFS 表现更好是正确的。

然而，对于情况 2，DFS 并不比 BFS 慢(至少在理论上是这样)，因为您可以简单地将每个节点存储在其相应的级别，然后它们稍后比较每个级别中的所有节点。然而，对于空间复杂度，BFS 会更好，因为一旦完成一个级别并移动到下一个级别，您就不必存储任何父节点。出于这个原因，BFS 可以推荐用于情况 2。