c++深度优先搜索DFS

这篇具有很好参考价值的文章主要介绍了c++深度优先搜索DFS。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

介绍

实现过程

模板

例题详解

1.枚举排列

2.迷宫寻路

3.八皇后

剪枝与优化

作业


今天我们来学习一个极其重要的算法:深度优先搜索。

介绍

深度优先搜索,又叫DFS,是遍历图或者数的一种算法,本质就是递归。具体方法:先以一个节点为起点,向一个方向扩展,再以新的节点为起点,向一个方向扩展,直到这个方向不满足条件,或者到达这个方向的最深,再往回走,叫做回溯。然后扩展另一个方向,知道整个图都遍历完成。所以叫做深度优先搜索。

这种算法极其重要,是每一个会编程的人都必须掌握的一种算法。因为许多东西都可以用它来实现。比如树的遍历,图的遍历,全排列。而且很多题目,如果你不会或者想不出正解,就可以用深搜暴力一下,也能得部分分。而且加上一定的优化和剪枝,通常能得不少分。

实现过程

深搜就是每次从一个点开始,枚举下一个节点,如果合法就深搜下一个点,并将深度加一。如果深度超出范围,就保存答案,并返回。每次搜下一个点时需要打上访问标记,防止在这一条路上再次访问这个点。注意,是在这条路上!今后在别的路上还是可以访问这个点的,所以搜完这条路需要删除访问标记,让从另一条路来的时候还可以访问这个点,这就是回溯。问了方便理解,我配了几张图来辅助解释。

首先,我们从A点开始,A点可以向下访问F、G两个点。

c++ dfs,# c++基础算法,c++,算法,深度优先

发现F点合法,我们先访问F点。

c++ dfs,# c++基础算法,c++,算法,深度优先

 然后从F点开始,可以访问D、E点,我们先访问E点。

c++ dfs,# c++基础算法,c++,算法,深度优先

 同样,E可以走到D、C、G,但是F已经访问过,有了访问标记,就不能走了。所以我们走C点

c++ dfs,# c++基础算法,c++,算法,深度优先

C点只与A、D、E相连,我们一个一个去试,如果合法就访问。

c++ dfs,# c++基础算法,c++,算法,深度优先

发现A点有了访问标记,所以不能走,返回,找下一个点。 

c++ dfs,# c++基础算法,c++,算法,深度优先

还剩下D,就访问他了。 但是D点只与C、E、F相连,而他们都有了访问标记,所以D这个点走不通,只好回头。

c++ dfs,# c++基础算法,c++,算法,深度优先

现在回到了C点,发现C点也无路可走,因为D点刚刚试过走不通,其他点又都有访问标记,这就证明C点也走不通,只好返回E点。

c++ dfs,# c++基础算法,c++,算法,深度优先

 再从E点访问其他的点。 

后面就是按照前面的进行一步步模拟,然后访问完所有的点。知道了实现过程,我们就结合具体的题目详细讲解吧!

模板

在讲题目之前,我先把深搜的模板列出,方便大家进一步理解,并将思路转化成代码。下面是深搜的模板:

void dfs(int num, int deep){//num为遍历的节点,deep为节点深度。 
	if(deep > max_deep){//超出最大深度。 
		保存答案。 
		return;
	}
	枚举下一个节点 i ,i满足未访问并且满足特定条件。 
	v[i] = 1;//i节点标记为已访问。 
	dfs(i, deep + 1);
	v[i] = 1;//回溯,下一次从不同的路来还能访问。这一步看具体题目,有些题目就无需回溯。 
}

其中回溯有部分题目不需要,因为回溯就是为了下一次还能从不同的道路访问这个点,而有些情况下一个点可能只访问一次。所以回溯与否需要自己判断,不过大部分题目都是需要回溯的。这u需要自己判断,而理解了回溯后你基本就理解了深搜了。

例题详解

1.枚举排列

题目描述

今有 nn 名学生,要从中选出 kk 人排成一列拍照。

请按字典序输出所有可能的排列方式。

输入格式

仅一行,两个正整数 n, kn,k。

输出格式

若干行,每行 kk 个正整数,表示一种可能的队伍顺序。

输入输出样例

输入 #1

3 2

输出 #1

1 2
1 3
2 1
2 3
3 1
3 2

说明/提示

对于 100% 的数据,1≤k≤n≤10。

看到这一题,我们先想要哪些参数。其实只要一个,就是当前搜到的位数。

只要一位一位得搜,当位数超出了 k 时,就代表搜到了答案。每次搜将这一位的结果保存到数组里,搜完输出数组结果。当然,要将每一位用到的数加上访问标记,然后回溯。

一下是遮体的代码:

#include<bits/stdc++.h>
using namespace std;
int n, k, p = 1;
int ch[1005];
bool use[1005];
void dfs(int pos){
	if(pos == k + 1){
		for(int i = 1; i <= p - 1; i++){
			cout << ch[i] << " ";
		}
		cout << endl;
		return;
	}
	for(int i = 1; i <= n; i++){
		if(!use[i]){
			ch[p++] = i;
			use[i] = 1;
			dfs(pos + 1);
			p--;
			use[i] = 0;
		}
	}
	return;
}
int main(){
	cin >> n >> k;
	dfs(1);
	return 0;
}

可以看到,回溯不仅仅是去除访问标记,还将存储答案的数组也回溯了。这是因为这次搜到的答案不能对下次有影响,就相当于清空了数组,只不过回溯是只清除了当前这一位。

2.迷宫寻路

题目描述

机器猫被困在一个矩形迷宫里。

迷宫可以视为一个 n×m 矩阵,每个位置要么是空地,要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。

机器猫初始时位于(1,1) 的位置,问能否走到 (n,m) 位置。

输入格式

第一行,两个正整数 n,m。

接下来 n 行,输入这个迷宫。每行输入一个长为 m 的字符串,# 表示墙,. 表示空地。

输出格式

仅一行,一个字符串。如果机器猫能走到 (n,m),则输出 Yes;否则输出 No

输入输出样例

输入 #1

3 5
.##.#
.#...
...#.

输出 #1

Yes

说明/提示

样例解释

路线如下:(1,1)→(2,1)→(3,1)→(3,2)→(3,3)→(2,3)→(2,4)→(2,5)→(3,5)。

数据规模与约定

对于 100% 的数据,保证 1≤n,m≤100,且 (1,1) 和 (n,m) 均为空地。

这一题是比较经典的深搜了。而且还有一个坑点。我们先思考搜索函数有拿哪些参数。就是 x 和 y ,表示当前搜到的横、纵坐标。

然后我们判断当前点是否是终点,如果是,就将 flag 设为1,代表这个地图可以走通。如果不是重点,那我们就枚举下一个点并搜索。怎么枚举下一个点呢?如果我们规定向上纵坐标减一,向下加一,向左横坐标减一,向右加一。那我们就可以用一个数字来表示横、纵坐标的加减情况。

int dx[] = {-1, 0, 1, 0},
	dy[] = {0, -1, 0, 1};

每次用当前的坐标加上 dx[i], dy[i],就获得了向左、上、右、下的点的坐标。

然后我们判断当前点是否合法。就是判断点是否超出了地图,是否是‘.’,也就是能走,是否被走过了。这样我们就得到了一个 check() 函数:

bool check(int x, int y){
	return (!u[x][y] && ch[x][y] == '.' && x > 0 && y > 0 && x <= n && y <= m);
}

如果当前点 check 合法,就将这个点标记为访问,并搜索这个点。

最后我们判断 flag 的情况,如果为1,就说明走到过终点,输出 Yes ,否则输出 No 。这样我们就得到了一个最初版的代码:

#include<bits/stdc++.h>
using namespace std;
int dx[] = {-1, 0, 1, 0},
	dy[] = {0, -1, 0, 1};
int n, m;
bool u[105][105], flag;
char ch[105][105];
bool check(int x, int y){
	return (!u[x][y] && ch[x][y] == '.' && x > 0 && y > 0 && x <= n && y <= m);
}
void dfs(int x, int y){
	if(x == n && y == m){
		flag = 1;
		return;
	}
	for(int i = 0; i < 4; i++){
		int xx = dx[i] + x;
		int yy = dy[i] + y;
		if(check(xx, yy)){
			u[xx][yy] = 1;
			dfs(xx, yy);
			u[xx][yy] = 0;
		}
	}
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> ch[i][j];
		}
	}
	dfs(1, 1);
	if(flag){
		cout << "Yes" << endl;
		return 0;
	}
	cout << "No" << endl;
	return 0;
}

为什么说是最初版呢?因为

c++ dfs,# c++基础算法,c++,算法,深度优先

啊这,很明显,朴素的算法不能通过,我们需要优化。

大家可以先想一下怎么优化。

1. 第一个优化比较好想到,就是我们每次搜索时判断是否到过终点。如果已经到过终点,也就是 flag = 1,那么就不需要搜下去了,直接返回。因为再搜下去也不会对结果产生影响。

基于这个思路,我们再提交一次代码:

#include<bits/stdc++.h>
using namespace std;
int dx[] = {-1, 0, 1, 0},
	dy[] = {0, -1, 0, 1};
int n, m;
bool u[105][105], flag;
char ch[105][105];
bool check(int x, int y){
	return (!u[x][y] && ch[x][y] == '.' && x > 0 && y > 0 && x <= n && y <= m);
}
void dfs(int x, int y){
	if(flag) return;
	if(x == n && y == m){
		flag = 1;
		return;
	}
	for(int i = 0; i < 4; i++){
		int xx = dx[i] + x;
		int yy = dy[i] + y;
		if(check(xx, yy)){
			u[xx][yy] = 1;
			dfs(xx, yy);
			u[xx][yy] = 0;
		}
	}
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> ch[i][j];
		}
	}
	dfs(1, 1);
	if(flag){
		cout << "Yes" << endl;
		return 0;
	}
	cout << "No" << endl;
	return 0;
}

结果:

c++ dfs,# c++基础算法,c++,算法,深度优先

哇,没错,我们就加上了一行代码,就从10pts到了20pts。别小瞧这10分,考场上能救你命(doge)。

所以我们还要优化。

2.这次的优化有点伤脑筋,希望大家好好想一想再看下去。

好的,其实我们可以在回溯上面动手脚(bushi)。我们再想一想回溯的作用:让下一次从别的路径过来时还能访问这个点。那我们这次还需要再次访问这个点吗?答案是否定的,因为如果我们访问了这个点,也就能确定从这个点能不能走向终点,不管从哪条路走到这个点,都不能改变这个点能走向终点或是不能。所以我们就可以去掉回溯!

所以程序3.0版本就有了

#include<bits/stdc++.h>
using namespace std;
int dx[] = {-1, 0, 1, 0},
	dy[] = {0, -1, 0, 1};
int n, m;
bool u[105][105], flag;
char ch[105][105];
bool check(int x, int y){
	return (!u[x][y] && ch[x][y] == '.' && x > 0 && y > 0 && x <= n && y <= m);
}
void dfs(int x, int y){
	if(flag) return;
	if(x == n && y == m){
		flag = 1;
		return;
	}
	for(int i = 0; i < 4; i++){
		int xx = dx[i] + x;
		int yy = dy[i] + y;
		if(check(xx, yy)){
			u[xx][yy] = 1;
			dfs(xx, yy);
		}
	}
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> ch[i][j];
		}
	}
	dfs(1, 1);
	if(flag){
		cout << "Yes" << endl;
		return 0;
	}
	cout << "No" << endl;
	return 0;
}

 这次终于如愿以偿:
c++ dfs,# c++基础算法,c++,算法,深度优先

 看到一片绿我就兴奋(doge)。

我们再想一下,为什么其它的搜索需要回溯呢?其实因为我们搜索的目的不同,这一题我们只需要知道是否能到达终点,所以从哪个点过来结果都是一样的。但是有些题目如果求的是最短路,那么从不同的点过来的结果就可能不同,所以我们需要回溯。

3.八皇后

题目描述

一个如下的 6×6 的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

c++ dfs,# c++基础算法,c++,算法,深度优先

上面的布局可以用序列 2 4 6 1 3 5 来描述,第 i 个数字表示在第 i 行的相应位置有一个棋子,如下:

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出,解按字典顺序排列。
请输出前 3 个解。最后一行是解的总个数。

输入格式

一行一个正整数 n,表示棋盘是 n×n 大小的。

输出格式

前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。

输入输出样例

输入 #1

6

输出 #1

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

说明/提示

【数据范围】
对于 100% 的数据,6≤n≤13。

题目翻译来自NOCOW。

USACO Training Section 1.5

 

这是一道很经典的深搜题,可以说会深搜都掌握了这道题。我们也从这道题向难题进发。

首先还是思考搜索函数有哪些参数,我们只需要一个 pos ,代表我们搜到了哪一行。所以结束条件就是行号 = n + 1。然后我们需要注意,这一题的访问标记不是简简单单的将这个点的坐标存起来,因为每一行、每一列、每一对角线都不能有超过一个棋子。也就是我们要用三个数组,来记录每一行、每一列、每一对角线是否有棋子。

然后就是怎么存储答案了。我们枚举的时候就把行号作为下标,列号作为值,存在一个数组里。这样只要输出数组里得知就可以了。

这一题没什么坑点,主要是熟练掌握深搜模板。下面是代码:

#include<bits/stdc++.h>
using namespace std;
int n, sum, a[105], b[105], c[105], d[105];
void dfs(int pos){
	if(pos == n + 1){
		sum++;
		if(sum <= 3){
			for(int j = 1; j <= n; j++){
				cout << a[j] << " ";
			}
			cout << endl;
		}
		return;
	}
	for(int i = 1; i <= n; i++){
		if(!b[i] && !c[pos + i] && !d[pos - i + n]){
			a[pos] = i;
			b[i] = c[pos + i] = d[pos - i + n] = 1;
			dfs(pos + 1);
			b[i] = c[pos + i] = d[pos - i + n] = 0;
		}
	}
	return;
}
int main(){
	cin >> n;
	dfs(1);
	cout << sum << endl;
    return 0;
}

剪枝与优化

剪枝就是对深搜的优化。在有些图中搜索完整个图会有很多很多冗余,比如在找最短路径时,我们每次在到达终点时记录最短距离,然后以后搜索时如果当前点到终点的距离加上已经走的距离已经超过最短的距离了,那么无论如何这条路也不会成为最短路径。我们直接 return 就好了。以上是一个比较简单的剪枝思路。

而优化主要就是记忆化搜索。我们把搜索函数中的某个参数存在数组里,比如你已经搜索得知了这个点到终点的最短距离,就无需再搜索下去,直接返回保存过的这个点到终点的距离就好了。

以上只是很简单的思路,真正的优化是很复杂的,以后会专门为这个写一篇文章。

作业

我搜集了几道比较好的搜索题,大家可以自己练习巩固。难度由易到难

  1. p1135奇怪的电梯。
  2. p1562还是n皇后。
  3. p1074靶形数独

以及一个无需回溯的搜索:p1331海战

以上这几题如果你能独立做出来,并且每题控制在一小时以内,那么你的深搜就完结~撒花。文章来源地址https://www.toymoban.com/news/detail-795592.html

到了这里,关于c++深度优先搜索DFS的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】图遍历算法 ( 深度优先搜索 DFS | 深度优先搜索和广度优先搜索 | 深度优先搜索基本思想 | 深度优先搜索算法步骤 | 深度优先搜索理论示例 )

    图 的 遍历 就是 对 图 中的 结点 进行遍历 , 遍历 结点 有如下两种策略 : 深度优先搜索 DFS 广度优先搜索 BFS \\\" 深度优先搜索 \\\" 英文名称是 Depth First Search , 简称 DFS ; DFS 基本思想 : 访问第一个邻接结点 : 从 起始点 出发 , 该 起始点 可能有 若干 邻接结点 , 访问 第一个 邻接结点

    2024年02月02日
    浏览(46)
  • c++深度优先搜索DFS

    目录 介绍 实现过程 模板 例题详解 1.枚举排列 2.迷宫寻路 3.八皇后 剪枝与优化 作业 今天我们来学习一个极其重要的算法:深度优先搜索。 深度优先搜索,又叫DFS,是遍历图或者数的一种算法,本质就是递归。具体方法:先以一个节点为起点,向一个方向扩展,再以新的节

    2024年01月16日
    浏览(41)
  • 深度优先搜索(DFS)算法

    目录 算法思想 时间复杂度和空间复杂度 算法实现 算法优缺点 应用领域 深度优先搜索(DFS)算法的思想是从图的某个起始顶点开始,沿着一条路径尽可能深入地访问图中的所有顶点,直到不能继续为止,然后返回并探索其他路径。具体而言,DFS算法使用栈数据结构来实现,

    2024年02月05日
    浏览(45)
  • 深度优先搜索(DFS)(算法笔记)

    本文内容基于《算法笔记》和官方配套练题网站“晴问算法”,是我作为小白的学习记录,如有错误还请体谅,可以留下您的宝贵意见,不胜感激。 深度优先搜索是一种枚举所有完整路径以遍历所有情况的搜索方法,总是以“深度”作为前进的。实现方式是有很多,最

    2024年02月08日
    浏览(50)
  • C++ 更多的DFS深度优先搜索...

    目录 DFS模版 剪枝 DFS的两种状态 使用全局变量存储 使用函数参数存储传递 众所周知,DFS是一种省督有限搜索,可以想象成一棵树根节点K开始递归到最深层的节点,通常用来枚举符合题目的所有可能情况或者个数。 话说,这个代码和全排列有什么不同吗哈哈哈哈哈 剪枝时

    2024年02月13日
    浏览(66)
  • [算法日志]图论: 深度优先搜索(DFS)

    ​ 深度优先搜索算法是一种遍历图这种数据结构的算法策略,其中心思想是朝图节点的一个方向不断跳转,当该节点无下一个节点或所有方向都遍历完时,便回溯朝上一个节点的另一个方向继续遍历。这种搜索策略与回溯法有异曲同工之妙。 正因为和回溯法有相似之处,所

    2024年02月03日
    浏览(62)
  • 【算法详解 | DFS算法】深度优先搜索解走迷宫问题 | 深度优先图遍历

    by.Qin3Yu 本文需要读者掌握 结构体 和 栈 的操作基础,完整代码将在文章末尾展示。 特别声明:本文为了尽可能使用简单描述,以求简单明了,可能部分专有名词定义不准确。 栈相关操作可以参考我的往期博文: 【C++数据结构 | 栈速通】使用栈完成十进制数转二四八进制数

    2024年02月03日
    浏览(49)
  • 第一周算法训练(dfs)(深度优先搜索算法)

    dfs: 深度优先搜索算法 ,是一种用于遍历或 搜索树或图的算法 .沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被

    2024年02月20日
    浏览(49)
  • 图的遍历(搜索)算法(深度优先算法DFS和广度优先算法BFS)

    从图的某个顶点出发访问遍图中所有顶点,且每个顶点仅被访问一次。(连通图与非连通图) 1、访问指定的起始顶点; 2、若当前访问的顶点的邻接顶点有未被访问的,则任选一个访问之;反之,退回到最近访问过的顶点;直到与起始顶点相通的全部顶点都访问完毕; 3、若

    2024年01月17日
    浏览(47)
  • 【数据结构与算法】搜索算法(深度优先搜索 DFS和广度优先搜索 BFS)以及典型算法例题

    【数据结构与算法】系列文章链接: 【数据结构与算法】递推法和递归法解题(递归递推算法典型例题) 【数据结构与算法】系列文章链接: 【数据结构与算法】C++的STL模板(迭代器iterator、容器vector、队列queue、集合set、映射map)以及算法例题 【数据结构与算法】系列文章链

    2024年04月13日
    浏览(65)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包