算法学习——深度优先搜索（DFS）

# 简介

深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点 v 的所在边都己被探寻过，搜索将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。这种算法不会根据图的结构等信息调整执行策略。 —— 维基百科

个人觉得深度优先搜索（DFS）是非常符合直觉的一种搜索算法。

举一个简单的例子，假设 Alice 正在走迷宫，她只有一个人，因此她采取了这种策略：

不断向前走，如果遇到岔路口，那么就随便选择一条路口进入，并把自己已经探索过的位置做上标记，一直保持这个方法，直到确认某条路是死路，或者找到迷宫的出口。如果这条路是死路，那么就往回退到上一个路口，看看有没有没探索过的分支。一直这样走遍整个迷宫，就能够找到出口。

# DFS 的递归实现

# 问题示例

以一个问题为例：P1605 迷宫 - 洛谷

Luogu-P1605

这个问题的迷宫较小，可以通过 DFS 的递归实现来解决：

	#include <iostream>
	#include <vector>

	using namespace std;

	int counter = 0;

	void mazePathfinding(vector<vector<int> > &maze, const int n, const int m, const int x, const int y, const int finishX, const int finishY)
	{
	if ( (x < 0) \|\| (y < 0) \|\| (x >= n) \|\| (y >= m)) // 数组越界就相当于达到了迷宫的边缘
	{
	return;
	}
	if ( maze[x][y] == 1 ) // 撞墙
	{
	return;
	}
	if ( (x == finishX) && (y == finishY) ) // 如果走到了终点算一种解法计数器 + 1
	{
	counter++;
	return;
	}

	// 如果既不会走不通也没到终点那么就需要尝试继续向前探索迷宫了

	maze[x][y] = 1; // 先把目前的位置标记为已访问这里直接标记为 1 也就是墙

	mazePathfinding(maze, n, m, x-1, y, finishX, finishY); // 尝试向左走一步
	mazePathfinding(maze, n, m, x+1, y, finishX, finishY); // 尝试向右走一步
	mazePathfinding(maze, n, m, x, y-1, finishX, finishY); // 尝试向上走一步
	mazePathfinding(maze, n, m, x, y+1, finishX, finishY); // 尝试向下走一步

	maze[x][y] = 0; // 这一步把已访问的状态清除以免影响到之后的搜索
	}

	int main()
	{
	int N = 0, M = 0, T = 0;
	cin >> N >> M >> T; // 输入参数

	vector<vector<int> > maze(N, vector<int>(M)); // 创建迷宫
	maze.assign(N, vector<int>(M, 0)); // 默认置 0

	int startX = 0, startY = 0, finishX = 0, finishY = 0; // 起点终点坐标的输入
	cin >> startX >> startY >> finishX >> finishY;

	int tempX = 0, tempY = 0; // 输入障碍物坐标
	for (int i=0; i<T; i++)
	{
	cin >> tempX >> tempY;
	maze[tempX-1][tempY-1] = 1;
	}
	mazePathfinding(maze, N, M, startX-1, startY-1, finishX-1, finishY-1); //DFS 递归实现
	cout << counter;
	return 0;
	}

这个递归实现的逻辑非常简单：首先判断是否到达终止条件，如果没有，那么尝试往四个方向走，也就是进入下一层递归。

# 递归实现的特点

# 优点

- 实现简单而直观

# 缺点

- 面对大规模问题时容易造成深层递归，甚至造成栈溢出

未完待续

Algorithm