代码随想录 深度优先搜索理论基础

一、dfs与bfs的区别：

1.大致区别：

（1）dfs：紧着一个方向去搜，直到搜不下去再换方向（换方向的过程涉及到了回溯）。

（2）bfs：先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像的是广度四面八方的搜索过程。

二、dfs的搜索过程：

举例，如下图所示。

1.该图是一个无向图，要搜索从节点1到节点6的所有路径。

2.dfs搜索的第一条路径如下所示：

3.此时找到了节点6，该回头再去搜索其他方向了：

4.又到了节点6，再回头去搜索其他方向：

5.又找到了一条从节点1到节点6的路径，再回头：发现路径7、8和路径7、9都是死路，都走到了已经遍历过的节点。

6.那么节点2所连接的路径和节点3所连接的路径都已经走过了，撤销路径只能向上回退，去撤销当初节点4的选择，也就是撤销路径5改为路径10。

三、代码框架：由于dfs搜索紧着一个方向，且需要回溯，因此使用递归的方式实现是最方便的，代码框架如下所示。

void dfs(参数) { if (终止条件) { 存放结果; return; } for (选择：本节点所连接的其他节点) { 处理节点; dfs(图，选择的节点); // 递归 回溯，撤销处理结果 } }

四、深搜三部曲：

1.确定递归函数和参数：

void dfs(参数)

一般情况下，深搜需要二维数组的数组结构保存所有的路径，需要一维数组保存单一路径，这种保存结果的数组，可以定义为全局变量，以避免函数参数过多。

vector<vector<int>> result; // 保存符合条件的所有路径 vector<int> path; // 起点到终点的路径 void dfs (图，目前搜索的节点)

2.确认终止条件：防止出现死循环、栈溢出等问题。

if (终止条件) { 存放结果; return; }

3.处理当前搜索节点出发的路径：一般就是使用一个for循环去遍历当前搜索节点所能走到的所有节点。

for (选择：本节点所连接的其他节点) { 处理节点; dfs(图，选择的节点); // 递归 回溯，撤销处理结果 }