一、BFS的介绍
BFS（广度优先搜索，也可称宽度优先搜索）是连通图的一种遍历策略。因为它的基本思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域。
广度优先搜索（BFS）类似于二叉树的层序遍历算法，它的基本思想是：首先访问起始顶点v，然后由v出发，依次访问v的各个未被访问过的邻接顶点w1,w2,w3….wn，然后再依次访问w1，w2,…,wi的所有未被访问过的邻接顶点，再从这些访问过的顶点出发，再访问它们所有未被访问过的邻接顶点….以此类推，直到途中所有的顶点都被访问过为止。
二、BFS搜索的步骤
1、首先创建一个visit[ ]数组和一个队列q，分别用来判断该位置是否已经访问过及让未访问过的点入队；
2、初始化visit[ ]数组，清空q队列；
3、让起点start入队，并使该点的visit置1；
4、while（！q.empty()）{......}执行搜索操作，
a、取出队头元素后使队头元素出队，判断该元素是否为目标到达点；
b、如果是目标点，就返回结果（一般是最短时间、最短路径）；
c、如果不是目标点，就继续访问与其相邻的位置点，将可走的相邻的位置点入队，并更新visit[ ]数组；
三、BFS的应用
BFS算法一般应用于单源最短路径的搜索。
1、寻找非加权图（或者所有边权重相同）中任两点的最短路径。
2、寻找其中一个连通分支中的所有节点。（扩散性）
3、bfs染色法判断是否为二分图。
四、DFS的介绍
深度优先搜索算法（Depth First Search，简称DFS）：一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。
算法基本思想：
回溯法：（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
五：DFS的搜索步骤
1、创建一个空栈stack（用来存放节点）和一个空列表visit（用来存放已访问的节点）
2、依次将起始点及邻接点加入stack和visit中
3、poo出栈中最后进入的节点,从图中获取该节点的邻接点
4、如果邻接点不在visit中，则将该邻接点加入stack和visit中
5、输出pop出的节点
6、重复3、4、5，直至栈为空
六：BFS与DFS的区别
| 广度优先搜索(BFS) | 深度优先搜索(DFS) | |
| 1 | BFS在Graph中逐级访问节点。 | DFS访问图深度明智的节点。 它会访问节点，直到到达叶或没有未访问节点的节点为止。 |
| 2 | 在开始任何其他节点之前，必须先充分探究一个节点。 | 一旦发现另一个未探索节点，就会暂停对该节点的探索。 |
| 3 | 使用队列数据结构存储未探索的节点。 | 使用堆栈数据结构存储未探索的节点。 |
| 4 | BFS较慢，需要更多的内存。 | DFS更快并且需要更少的内存。 |
| 5 |
一些应用：
|
一些应用：
|