深度优先搜索与广度优先搜索 | 学习笔记

DFS深度优先搜索

搜索用法：

对空间进行遍历

特点：

利用栈 stack 进行搜索，空间占用为 $O(h)$ (h指树与图的高度)。尽量往子节点搜索，搜到头时回溯，同时查找是否能够进入其他子节点

例题：

acwing842-排列数字

int path[N];
// 用于存储搜索到的方案 
bool st[N];
// 用于存储当前的搜索情况中某个数是否被用过 

void dfs(int u)
// u 表示当前搜索进行到的层数 
{
	if (u == n) 
	// 如果填完了数，即搜索到最后一个子节点 
	{
		for (int i = 0; i < n; i ++)
			cout << path[i] << " ";
        // 对匹配成功的情况进行输出
		cout << endl;
		return;
        // 结束
	}
	
	for (int i = 1; i <= n; i ++)
		if (!st[i])
        // 括号内是搜索成功的条件，视题目而定
		{
			path[u] = i;
			st[i] = true;
			// 存储这一层的结果 
			dfs(u + 1);
			// 进行下一层搜索
			st[i] = false;
			// 恢复当前搜索的状态，回溯 
		}
}

剪枝的典型例题：

USACO1.5八皇后

解法1：按行搜索

时间复杂度 $O(n!)$

按行搜索放皇后时，我们需要为该点所在列，正反对角线打标记表示该列，正反对角线被占用

为此，我们需要找到每个点所在位置的列，正反对角线的表示规律：

对于列，可用 col[i] 表示

对于正对角线，发现在同一条对角线上，横纵坐标相加的和总是相等的，因此我们可以使用 dg[u + i] 表示当前正对角线

对于反对角线，发现横纵坐标之差总是相等的，因此我们可以使用 udg[i - u] 来表示当前反对角线。此时问题出现了，$i$ 是可以小于 $u$ 的

数组下标写错，可是会 RE 得很惨

因此我们将所有的下标右移 $n$ ，从而保证数组下标恒正，因此要注意开两倍的数据范围 $N$

const int N = 20;
// 以数据范围为 9 的情况举例

正解：

char g[N][N];
// 用于存储棋盘
bool col[N], dg[N], udg[N];
// 分别表示：列，正对角线(左下到右上)，反对角线 
void dfs(int u)
{
	if (u == n)
	{
		for (int i = 0; i < n; i ++)
			puts(g[i]);
		cout << endl;
		return;
	}
	
	for (int i = 0; i < n; i ++)
		if (!col[i] && !dg[u + i] && !udg[n - u + i])
		// 判断当前枚举到的点是否不与其他已经放的点冲突
		{
			g[u][i] = 'Q';
			col[i] = dg[u + i] = udg[n - u + i] = true;
			dfs(u + 1);
			col[i] = dg[u + i] = udg[n - u + i] = false;
			g[u][i] = '.';
		}
}

解法2：按点搜索

相较于解法1，此算法按点枚举是否可行，因此需要逐一判断行 row ，列 col ，正对角线 dg，反对角线 udg 是否冲突，并且时间复杂度也会起飞，达到 $O(2^{n^2})$

char g[N][N];
bool row[N], col[N], dg[N], udg[N];
// 分别表示：列，正对角线(左下到右上)，反对角线 
void dfs(int x, int y, int s)
// 分别表示 当前点的x坐标，当前点的y坐标，放到第几个皇后力
{
	if (y == n) y = 0, x ++;
	// 超出边界后换行
	if (x == n)
	// 图中无位置可放
	{
		if (s == n)
		// 皇后满足条件
		{
			for (int i = 0; i < n; i ++)
				puts(g[i]);
			puts("");
		}

		return;
		// 如果满足，那么输出答案后结束；如果不满足，那么直接结束
	}
	
	// 分类1：当前点不放皇后
	dfs(x, y + 1, s);

	// 分类2：当前点放皇后
	if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
	{
		g[x][y] = 'Q';
		row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
		dfs(x, y + 1, s + 1);
		row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
		g[x][y] = '.';
	}
}

BFS宽度优先搜索

特点：利用队列 queue 进行搜索，空间占用为 $O(2^h)$ 。同时搜索父节点下的每一个子节点，逐层递进。BFS搜索的特点是 具有最短性(即到从父节点到子节点的最短路最先搜到) 注意BFS解最短路时只适用于每条路权重相同的情况

csdn - 宽度优先搜索图解

例题：

acwing844-走迷宫

typedef pair<int, int> PII;
int map[N][N], d[N][N];
// map存储地图，d存储每一个点到起点的距离 
PII q[N * N];
// 模拟队列，使用二元组存储
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
// 位置偏移向量

int bfs()
{
	int hh = 0,  tt = 0;
	q[0] = {0, 0};
	// 队列初始化
	memset(d, -1, sizeof d);
	// 初始化为 -1 的点表示没有走过 
	d[0][0] = 0;
	// 从左上角开始宽搜
	
	while (hh <= tt)
	// 队列不空 
	{
		auto t = q[hh ++];
		
		for (int i = 0; i < 4; i ++)
		{
			int x = t.first + dx[i], y = t.second + dy[i];
			// 位置偏移尝试
			if (x >= 0 && x < n && y >= 0 && y < m && !map[x][y] && d[x][y] == -1)
			// 合法条件：未出界，可以走，未走过
			{
				d[x][y] = d[t.first][t.second] + 1;
				q[ ++ tt ] = {x, y};
			}
		}
	}
	
	return d[n - 1][m - 1];
}

若要存储路线：

PII Prev[N][N];
// 用于存储当前点是从哪里走来的
Prev[x][y] = t;
// 在159行添加，存储当前点的上一个点

int x = n - 1, y = m - 1;
while (x || y)
// x == y == 0表示到达起点
{
	cout << x << ' ' << y << endl;
	x = Prev[x][y].first, y = Prev[x][y].second;
}
// 在163行添加，倒序输出路径