搜索

DFS · 深度优先搜索

定义

深度优先搜索属于图算法的一种，英文缩写为 DFS 即 Depth First Search. 其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

——百度百科

在一条路上的分岔按顺序选择方向，一条路走到底再返回到最近分岔选择下一条路，这个分岔下所有路全走完后再返回到更上一个分岔走下一条路。

基本思路

深度优先遍历图的方法是，从图中某顶点v出发：

1. 访问顶点 v ；
2. 依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
3. 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

搜索完节点后注意是否需要回溯！

模板

bool judge(int x, int y) {};	//判断当前状态是否合法

bool check(int x, int y) {};	//判断是否为最终答案

void dfs(int x, int y, int z)
{
    if(!judge(x, y)) return;
    if(check(x, y))
    {
        //保存答案
    }
    vis[x][y] = 1;	//标记已搜索过此节点，防止重复搜索
    /*
        操作...
    */
    dfs(x - 1, y, z + 1);
    dfs(x + 1, y, z + 1);
    dfs(x, y - 1, z + 1);
    dfs(x, y + 1, z + 1);
    vis[x][y] = 0;	//回溯
}

优化

剪枝

有些求最优解的题目，可以不用完全遍历，当目前 dfs 的解已经比历史遍历得到的最优解更差时，可以停止遍历，节省一部分时间复杂度。

bool judge(int x, int y) {};	//判断当前状态是否合法

bool check(int x, int y) {};	//判断是否为最终答案

void dfs(int x, int y, int z)
{
    if(!judge(x, y)) return;
    if(z >= ans) return;
    if(check(x, y))
    {
        ans = z;
        //保存答案
    }
    vis[x][y] = 1;	//标记已搜索过此节点，防止重复搜索
    /*
        操作...
    */
    dfs(x - 1, y, z + 1);
    dfs(x + 1, y, z + 1);
    dfs(x, y - 1, z + 1);
    dfs(x, y + 1, z + 1);
    vis[x][y] = 0;	//回溯
}

记忆化搜索

对于遍历某些确定的类型时，如果到达一个节点之后的遍历结果是可以确定的，第一遍先向下遍历得到结果，将这个结果保存，之后再遍历到此节点时直接返回已得到的结果，可以节省一部分时间复杂度。

如：洛谷 P1434 [SHOI2002]滑雪

题目大意：矩阵求最长下降线路长度

int fx[5] = { 0, 0, 0, 1, -1 };
int fy[5] = { 0, 1, -1, 0, 0 };
int dfs(int x, int y)
{
	if (f[x][y]) return f[x][y];	//记忆化搜索
	f[x][y] = 1;	//题目中答案是有包含这个点的
	for (int i = 1; i <= 4; i++)
	{
		int xx = fx[i] + x;
		int yy = fy[i] + y;	//四个方向
		if (xx > 0 && yy > 0 && xx <= n && yy <= m && a[x][y] > a[xx][yy])
		{
			f[x][y] = max(f[x][y], dfs(xx, yy) + 1);
		}
	}
	return f[x][y];
}

BFS · 广度优先搜索

定义

从出发点一层一层向外遍历，到达终点就结束。因此，到达终点的方案一定是最优解。

无论有多少条路，每条路都只走一步，并记录下状态，等到所有的路都走完一步后，再从第一条路开始走第二步，直至有一条路走到终点。

基本思路

广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形：

1. 把根节点放到队列的末尾。

2. 每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。

3. 找到所要找的元素时结束程序。

4. 如果遍历整个树还没有找到，结束程序。

模板

int fx[5] = { 0, -1, 1, 0, 0 };
int fy[5] = { 0, 0, 0, -1, 1 };	//上下左右
struct node
{
    int x, y, z;
};

bool check (int x, int y) {};	//判断点是否能走

void bfs(int x, int y, int z)
{
    node start;
	start.x = x;
	start.y = y;
	start.z = 0;	//start 为出发点，z 为步数
    queue <node> q;
	q.push(start);	//将出发点推入队列中等待处理
	while (!q.empty())
	{
        node now;
		now = q.front();	//从队列中取出首元素处理
		q.pop();	//将该元素取出后要记得推出，否则只推入不推出，死循环
		t[now.x][now.y] = now.z;	//这里是记录了到 [now.x][now.y] 的最短路径，也可以做其他操作
		for (int i = 1; i <= 4; i++)	//往四个方向继续遍历
		{
            if (check (now.x + fx[i], now.y + fy[i]))
			{
				node next;
				next.x = now.x + fx[i];
				next.y = now.y + fy[i];
				next.z = now.z + 1;
				vi[next.x][next.y] = 1;
				q.push(next);	//将该点保存并推入队列中，等待前面的处理完后再走下一步
			}
		}
	}
}

习题

A Find a way · HDU 2612

B Dungeon Master · POJ 2251

C Red and Black · HDU 1312

D Counting Sheep · HDU 2952

E N皇后问题 · HDU 2553

F A Funny Bipartite Graph · 计蒜客 42577

G wyh2000 and pupil · HDU 5285

H Legal or Not · HDU 3342