Jas*_*ker 24 algorithm search graph-theory breadth-first-search depth-first-search
通常当我不得不走图表时,由于空间复杂度较低,我总是使用深度优先搜索.我诚实从未见过呼吁广度优先搜索,但我的经验的情况是相当有限的.
什么时候使用广度优先搜索是有意义的？
更新:我想我的答案在这里表示我已经使用了BFS(因为我觉得这是一个DFS)的情况.我仍然很想知道,为什么它在这种情况下很有用.
sep*_*p2k 13
当您想要通过遍历尽可能少的边来到达节点时,即当您想要在未加权图中找到最短路径时.
此外,当例如每个节点仅具有一个子节点时,即当图形深但不是非常宽时,深度优先搜索的空间复杂度可以高于广度优先搜索的空间复杂度.
如果您的搜索域是无限的,则深度优先搜索不保证终止/找到解决方案,即使存在有限解决方案.
您还可以看到更精细的算法,如A*,作为广度优先搜索的特殊子类型.
通常,bfs既是最优的又是完整的(具有有限的分支因子),而dfs则不是.