广度优先搜索和深度优先搜索各有什么特点

广度优先搜索（BFS）的特点：

1. BFS是一种逐层扩展的搜索策略，从起点开始，先访问所有与起点距离为1的节点，然后访问距离为2的节点，以此类推，直到找到目标节点或遍历完整个图。
2. BFS可以找到最短路径，因为它先访问距离起点近的节点，如果目标节点在它们中间，则可以保证最先找到的路径是最短的。
3. BFS需要维护一个队列来存储待访问的节点，因此空间复杂度比深度优先搜索高。
4. BFS对于解决“状态转移”问题（如迷宫问题）比较有效，因为它可以找到最短路径。

深度优先搜索（DFS）的特点：

1. DFS是一种递归的搜索策略，从起点开始，访问一个节点后，递归访问它的未被访问的邻居节点，直到找到目标节点或遍历完整个图。
2. DFS不一定能找到最短路径，因为它是一种深度优先的搜索策略，有可能会先找到一条比较长的路径。
3. DFS只需要维护一个栈来存储待访问的节点，因此空间复杂度比BFS低。
4. DFS对于解决“生成问题”（如子集、排列问题）比较有效，因为它可以遍历所有可能的情况。