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 需要更少的内存。 |
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/264348.html