BFS 和 DFS 的区别

1. 广度优先搜索：

BFS 代表广度优先搜索，是一种基于顶点的技术，用于在图中查找最短路径。它使用先进先出的队列数据结构。在 BFS 中，每次访问并标记一个顶点时选择一个顶点，然后访问其相邻的顶点并将其存储在队列中。它比 DFS 慢。

例子：

 输入:
        A
       / \
      B   C
     /   / \
    D   E   F

输出结果：

A, B, C, D, E, F

2. 深度优先搜索：

DFS 代表深度优先搜索，是一种基于边缘的技术。它使用 Stack 数据结构并执行两个阶段，首先将访问的顶点压入堆栈，然后如果没有顶点，则弹出访问的顶点。

例子：

 输入:
        A
       / \
      B   C
     /   / \
    D   E   F

输出结果：

A, B, C, D, E, F

广度优先搜索和深度优先搜索的比较区别：

S.No	广度优先搜索	深度优先搜索
1	BFS 代表广度优先搜索。	DFS 代表深度优先搜索。
2	BFS(广度优先搜索)使用队列数据结构来寻找最短路径。	DFS(深度优先搜索)使用堆栈数据结构。
3	BFS 可用于在未加权图中找到单源最短路径，因为在 BFS 中，从源顶点到达具有最少边数的顶点。	在 DFS 中，可能会遍历更多边以从源到达目标顶点。
4	BFS 更适合搜索更接近给定源的顶点。	当有远离源的解决方案时，DFS 更适合。
5	BFS 首先考虑所有邻居，因此不适用于游戏或谜题中使用的决策树。	DFS 更适合游戏或解谜问题。通过这个决定探索所有路径。如果这个决定导致获胜的局面，就停下来。
6	BFS的时间复杂度在使用邻接列表时为O(V+E)，使用邻接矩阵时为O(V^2)，其中V代表顶点，E代表边。	DFS的时间复杂度在使用邻接列表时也是O(V + E)，使用邻接矩阵时也是O(V^2)，其中V代表顶点，E代表边。
7	兄弟姐妹节点先于子节点访问	子节点先于兄弟姐妹节点访问
8	BFS 中没有回溯的概念。	DFS算法是一种使用回溯思想的递归算法
9	BFS用于二分图、最短路径等各种应用。	DFS用于无环图、拓扑顺序等各种应用。
10	BFS 需要更多内存。	DFS 需要更少的内存。