BFS和DFS相关算法以及相关性质

定义

当我们在解决多状态问题时，我们可以把每一个状态抽象为一个节点，如果有两个状态$a,b$，a能够到达b，我们就建立一条从a到b的边。这样我们就能将这个问题转化为图论问题。

搜索算法本质是一种高级的枚举。按照一定的策略遍历构建的状态图来得到想要的答案。

常见的搜索形式

深度优先搜索DFS

基本定义

时间戳，即某个节点进栈的时间和出栈的时间，我们把一次出栈或者进栈认为是一个单位时间；

入栈时间戳即一个节点入栈时的时间节点，即对于节点$u$，$d(u)$为其入栈时间戳

出栈时间戳即一个节点出栈时的时间节点，即对于节点$u$，$f(u)$为其出栈时间戳

我们引入记号$S_r$表示有根树中以$r$为根节点的子树，显然$S_r$为一张图，故也可表达为$E_r(V_r,E_r)$

深度优先搜索的两种实现方式

在进行搜索时，我们往往会有一个搜索进入的入口，我们称为源点；而深度优先搜索顾名思义，即从源点开始不断的到达能够到达的点，直到在一定的规则下无法继续到达新的节点为止，然后回溯到能到达新节点的节点，继续进行类似的操作；当然有些时候我们搜索的图可能会很大（或者直接就是无穷大），此时当我们得到答案时就会退出搜索。下面是DFS的递归形式；

DFS(此处传入需要的参数){ if(判断边界条件){ 计算答案 退回上一层递归 } for i in 能够到达的点 if(判断是否满足条件）{ 修改操作; DFS(传入对应的参数); 回溯操作; } }

DFS的本质就是一个栈，每个节点都是先进后出的，所以我们也可以用非递归的栈来实现DFS；代码如下：

Stack为一个栈，s代表源节点 DFS(传入必要的参数){ Stack.push(s); while(!Stack.empty()){ head=stack.tail(); flag=0;//标记head节点是否拓展到了新的节点如栈 for i in head能够到达的点 if(判断是否满足条件){ 修改操作； 统计答案操作； Stack.push(i); flag=1; break; } if(flag==0) { Stack.pop(); 回溯操作 } } }

对于DFS我们的时间复杂度取决于我们具体的问题；

深度优先搜索的性质

(1)执行深度优先搜索的过程本质上是构建了一颗树，我们把这颗树称为深度优先搜索树；

(2)深度优先搜索树中的$S_r$中的所有节点的出栈和入栈的时间戳合在一起是连续的整数，并且$r_0$的入栈时间戳最小，出栈时间戳最大。

(3)节点时间戳区间定理，对于节点$u,v$,分别有时间戳区间$[d(u),f(u)],[d(v),f(v)]$,两个区间只有两种情况，包含关系，或者完全分离，如果$u$区间包含$v$区间则，$u$为$v$的祖先节点；

基于DFS的算法

（1）Tarjan系列算法：强连通系列，LCA

（2）拓扑排序算法（DFS版本）

（3）迭代深搜IDA*

迭代深搜的本质是深度优先搜索的变式，即在搜索时限制搜索的深度，同时利用已搜到信息来减枝。这样做最大的优点是能够提前结束对那些无法拓展到答案的分支的搜索，并且可能可以为下一次的迭代搜索提供减枝的信息；代码如下：

IDAstar(需要的参数){ deep//当前搜索的最大深度 while(得到答案){ dfs（deep） ++deep； } }

广度优先搜索BFS

BFS的实现

与深度优先搜索不同，广度优先搜索的时候，我们选择将当前能拓展的点都拓展放入队列中（先进先出）；下面是实现代码：

定义队列q； BFS(需要传入的参数){ 清空队列q； q.push(s)//加入源节点 while(!q.empty()){ now=q.front();q.pop(); 拓展与now相邻的节点； } }

BFS的性质

（1）DFS相同BFS也会形成一棵搜索树，我们称之为广度优先搜索树，但其与DFS搜索树不同的是，BFS搜索树构建的过程是按层扩展的，从第1层开始逐层扩展；

（2）BFS搜索树中第$i$层中的节点在原图上只可能与第$i-1$或者$i+1$层有边；

（3）BFS能够保证从源节点到当前放入栈中的每一个节点都是最短步数；

基于BFS的算法

（1）最短路算法Dijkstra

（2）拓扑排序

（3）最大流Dinic算法（构建分层图）

（4）A*算法

A*算法可以看做是广搜的变式，其本质是将当前可拓展的点放入一个优先队列中，然后优先增广优先队列中最优的点，而问题的关键是对于优先队列的比较规则的设定，即估计函数的设计，一般而言估计函数的核心是估计到达终点状态的代价$f(n)$。只有$f(n)$不大于实际代价的时候，才能保证算法的正确性。