dfs与bfs简单辨析

概述

dfs即深度优先搜索(deep first search)与bfs即宽度优先搜索(breadth first search)究竟有哪些不同，本文将会依据我自己的理解，做出一定深度的阐述。

首先，需要大家清楚，dfs通常与栈这种数据结构相联系，bfs则与队列联系紧密，这两种数据结构的特性决定了其与算法内在必然的关系。两种搜索算法都应用了递归的思想，所以有相关知识的浏览者能够很快理解。

接下来我将结合具体图形进行分析。

正文

dfs

我们以该二叉树为例结合堆栈示意图，先讲解dfs递归的过程。

首先我们将整棵树的根节点即1节点入栈。

然后查找1节点下是否有子节点，发现了2节点，我们把2节点入栈。

如此查找到4节点下有子节点7，7节点下没有子节点，此时栈中已经有了四个节点。

7节点下没有子节点，代表该路径已经到底，所以向上一层回溯，7节点出栈，查询4节点有没有除7节点外的子节点，发现8节点，8节点入栈。

这时对8节点查询，发现8节点并没有子节点，向上回溯，到4节点，发现4节点也没有其余子节点，继续回溯，找到2节点，查询2节点。通过查询2节点，发现了2节点下的5节点，以及5节点下的9节点。

对9节点查询，无子节点，回溯到5节点，回溯到2节点，发现2节点无其余子节点，回溯到1节点，查询后发现3节点，6节点，10节点这条路。回溯到6节点，又发现3节点，6节点，11节点这条路。最后回溯到根节点1，搜索工作完成。

通过这个过程可以明显的感觉到深度优先搜索是一种一条路走到黑的搜索算法。

bfs

我们以同一棵二叉树为例，配合队列示意图，进行bfs的讲解。

首先同样将根节点即1节点入队。

与dfs不同的是，我们不再只盯着1节点的某一个子节点，而是将所有1的子节点入队，很明显1的子节点有2节点和3节点，所以将2节点和3节点入队。与此同时，1节点完成了自己的使命，1节点出队。

这时用同样的操作处理队首，即当前处于队首位置的2节点，搜索2节点的子节点可知4节点和5节点，将4、5两节点入队，2节点出队。

搜索3节点，6节点入队，3节点出队。

然后是7、8两节点入队，4节点出队。

然后5节点出队，5节点的子节点9节点入队，6节点出队，10节点和11节点入队。

7节点到了队首的位置，对7节点进行搜索，发现7节点没有子节点，则只进行7节点的出队操作。同理，当前队列中五个节点全部出队之后，队列变成了空队列，广度搜索过程结束，搜索工作完成。

而通过bfs，我们可以很清楚的感觉到，bfs完整的进行同层操作，在当前层的节点全部遍历后才会处理下一层的节点。