宽度优先搜索与深度优先搜索有何区别?

宽度优先搜索和深度优先搜索是两种不同的图遍历算法。宽度优先搜索逐层扩展节点，先访问离起点近的节点；深度优先搜索则沿着一条路径深入探索，直到无法继续再回溯。

区别

宽度优先搜索：它使用队列数据结构，按照层次顺序访问节点。比如从起点开始，先访问所有直接相邻的节点，再访问这些节点的相邻节点。这种方法能找到最短路径，适合解决最短路径问题，但需要较多内存存储待访问节点。

深度优先搜索：它使用栈或递归，沿着一条路径尽可能深地探索。比如从起点开始，选择一个方向一直走到底，再回溯到分叉点选择其他方向。这种方法内存占用较少，适合解决连通性问题或拓扑排序，但可能找不到最短路径。