深度优先搜索(DFS)算法

发表于 阅读次数： 阅读次数： Valine：

前言

最近学习了深度优先搜索（DFS）算法，特写此文章，以供未来的复习和归纳。

算法解释

深度优先搜索属于图算法的一种，英文缩写为DFS，即Depth First Search。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止后回溯，而且每个节点只能访问一次。
以下图为例，从根节点A进行深度优先搜索，目标为G。可以得到的搜索过程如下：A->C->F（回溯至A）A->B->E（回溯至B）B->D->G搜索完成。需要注意的是，回溯前必须将已访问的节点进行标记，否则将会陷入死循环。
mpB7uT.png

基本框架

1
2
3
4
5
6
7
8
9
10
11
void dfs(int dep,[状态]){
	if(当前是目标状态) 输出解或者作计数、评价处理;
	else 
		for(int i = 0; i < 状态的转移可能数; ++i)
		{
			保存现场(断点,维护参数表);
			if(第i种状态拓展可行) 
				dfs(dep+1,[新状态]);
			恢复现场(回溯,回到上一个状态);
		}
}

例题

在n*m棋盘上有一中国象棋中的马，马走日，且只能向右走。
请你找出一条可行路径，使得马可以从棋盘的左下角（1,1）走到右上角（n，m）。
输入样例
9 5
输出样例
(1,1)->(3,2)->(5,1)->(6,3)->(7,1)->(8,3)->(9,5)

根据dfs算法，我们可以得知：
1.在无法确定走哪条线路的时候，任选一条线路进行尝试；
2.当从某点出发，所有可能到达的点都不能到达终点时，说明此点是一个死节点，必须回溯到上一个点，并重新选择一条新的线路进行尝试。
对于这样的一种能走下去就继续向下走的策 略，就是我们常说的深度优先搜索，即DFS。

因此，我们可以利用递归思想写出以下dfs函数

1
2
3
4
5
6
7
8
9
10
11
12
13
void dfs(int dep){//跳了dep步跳到qd。
	if(qd.x==zd.x&&qd.y==zd.y){
		cout<<"success "<<dep<<endl;
		return; 
	}
	else
		for(int i=0;i<4;i++)
			if(check(qd,dx[i],dy[i] ){
				qd.x+=dx[i]; qd.y+=dy[i]; //状态转移
				dfs(dep+1);
				qd.x-=dx[i]; qd.y-=dy[i]; //恢复状态
			}		
}