浅析DFS与BFS的异同/图的和深度优先遍历和广度优先遍历有什么不同

一、深度优先遍历（DFS）

1.定义

图的深度优先搜索遍历(DFS)类似于二叉树的先序遍历。它的基本思想是:首先访问出发点v,
并将其标记为已访问过;然后选取与v邻接的未被访问的任意一个顶点w，并访问它:再选取与w邻接
的未被访问的任一项点并访问，以此重复进行。当一个顶点所有的邻接顶点都被访问过时，则依次退回到最近被访问过的顶点，若该顶点还有其他邻接顶点未被访问，则从这些未被访问的顶点中取一一个并重复上述访问过程，直至图中所有顶点都被访问过为止。图7-8所示即为一个图的深度优先搜索遍历过程。

图及定义摘自天勤，天勤no.1.

二、广度优先遍历（BFS）

1.定义

图的广度优先搜索遍历(BFS) 类似于树的层次遍历。它的基本思想是:首先访问起始顶点V,然
后选取与v邻接的全部顶点w，… w。进行访问，再依次访问与WI，… w。邻接的全部顶点(已经
访问过的除外)，以此类推，直到所有顶点都被访问过为止。
广度优先搜索遍历图的时候，需要用到一一个队列(二叉树的层次遍历也要用到队列)，算法执行过程
可简单概括如下:
1)任取图中一个顶点访问，入队，并将这个顶点标记为已访问;
2)当队列不空时循环执行:出队，依次检查出队顶点的所有邻接顶点，访问没有被访问过的邻接顶
点并将其入队;
3)当队列为空时跳出循环，广度优先搜索即完成。

三、异同

1.相同点

时间复杂度是相同的！
时间复杂度是相同的！
时间复杂度是相同的！
书上没有明确指明这一点，但是严奶奶的数据结构写到：

图源https://www.cnblogs.com/hi3254014978/p/12627861.html

2.不同点

（1）DFS

1. 提供回溯，可以更新，完成并查集等算法
2. 适用于有条件约束的问题，如棋盘问题
3. 可以判断是否连通

（2）BFS

1. 求最短路径
2. 迷宫问题等

先挖个坑，有机会再逐渐补充完善。