devbox
weixin_40725706
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【算法】深度优先搜索DFS 入门：基本知识+经典例题_根据一个起始点写出深度优先序列例题

作者：weixin_40725706 | 2024-05-20 06:40:31

赞

踩

根据一个起始点写出深度优先序列例题

DFS最重要的是理清搜索顺序！
ps：这是我入门dfs时写的博客，后来dfs渐渐熟练了，也补充了一些题目上去（带原题和代码）。个人感觉整篇博文从上到下确实由易到难，代码也由开始的冗长变得渐渐精简。

自学DFS看的视频：
小甲鱼：讲原理
青岛大学-王卓：讲的较为全面的基本知识p122-124
自学之后的题目总结：【DFS】题目总结

推荐AcWing y总的讲解！

基本知识

深度优先搜索(DFS, Depth First Search)是一个针对图和树的遍历算法。早在19世纪就被用于解决迷宫问题。

它的思想是从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。（参考“可参考资料2”）

对图的理解可见：
图的详解

大概步骤：

深度优先搜索用一个数组存放产生的所有状态。
（1） 把初始状态放入数组中，设为当前状态；
（2） 扩展当前的状态，产生一个新的状态放入数组中，同时把新产生的状态设为当前状态；
（3） 判断当前状态是否和前面的重复，如果重复则回到上一个状态，产生它的另一状态；
（4） 判断当前状态是否为目标状态，如果是目标，则找到一个解答，结束算法。
（5） 如果数组为空，说明无解。
对于pascal语言来讲，它支持递归，在递归时可以自动实现回溯（利用局部变量）所以使用递归编写深度优先搜索程序相对简单，当然也有非递归实现的算法。（摘自百度百科）

经典例题

1、水池问题

很基础的水池问题

题目描述
输入
第一行输入一个整数N，表示共有N组测试数据
每一组数据都是先输入该地图的行数m(0<m<100)与列数n(0<n<100)，
然后，输入接下来的m行每行输入n个数，表示此处有水还是没水（1表示此处是水池，0表示此处是地面）

输出
输出该地图中水池的个数。

每个水池的旁边（上下左右四个位置）如果还是水池的话的话，它们可以看做是同一个水池。
样例输入
2
3 4
1 0 0 0
0 0 1 1
1 1 1 0
5 5
1 1 1 1 0
0 0 1 0 1
0 0 0 0 0
1 1 1 0 0
0 0 1 1 1
样例输出
2
3

一个总结：
这是一道基础dfs题，适合我这样的初学者；
大致思路是：
定义一个void dfs()函数，功能是如果二维数组某点为1，则判断其上下左右是否为为1，若为1，使之为0，并递归调用dfs对其周围进行搜索判断；
其中，若传入一个已知为1的点，对它周围搜索，肯定会搜索会本点并使之为0，则无需单独对该点单独操作；
且，if中的数组的参数与调用时传入的参数相同，如此方便记忆。

void函数如：

void dfs(int a,int b)                                   //深度优先搜索函数，一旦调用，一个点周围连续的地方都记为0； 
{
	if(arr[a-1][b]==1){arr[a-1][b]==0;dfs(a-1,b);        //上 
	}
	
	if(arr[a+1][b]==1){arr[a+1][b]==0;dfs(a+1,b);        //下 
	}
	
	if(arr[a][b-1]==1){arr[a][b-1]==0;dfs(a,b-1);        //左 
	}
	
	if(arr[a][b+1]==1){arr[a][b-1]==0;dfs(a,b+1);         //右 
	} 
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

主函数：
int main(void)要传入void（目前不知道原因，记就是了）
此题的常规操作：
输入多组数据用while(t--)

逐个传入二维数组常规操作：

for(int i=1;i<=n;i++)            //逐个输入二维数组的常规操作 
		{
			for(int j=0;j<=m;j++)
			{
				cin>>arr[i][j];
			}
		}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

遍历二维数组也要两层循环，其中从1开始，因为我们计数从1开始，简化操作；
i、j均小于等于；

for(int i=1;i<=n;i++)
{
	for(int j=1;j<=m;j++)
	{......}

}

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

其他操作：
1、万能头；
2、可以宏定义一个N表示水池的边界，其中105是从1到100再上下左右+1 为105（自行体会）；

#include<bits/stdc++.h>        //万能头
#define N 105 

  • 1
  • 2

还可以再看看链接里的讲解；

整体代码：

#include<bits/stdc++.h>        //万能头
#define N 105 
using namespace std;

int arr[N][N];

void dfs(int a,int b)                                   //深度优先搜索函数，一旦调用，一个点周围连续的地方都记为0； 
{
	if(arr[a-1][b]==1){arr[a-1][b]==0;dfs(a-1,b);        //上 
	}
	
	if(arr[a+1][b]==1){arr[a+1][b]==0;dfs(a+1,b);        //下 
	}
	
	if(arr[a][b-1]==1){arr[a][b-1]==0;dfs(a,b-1);        //左 
	}
	
	if(arr[a][b+1]==1){arr[a][b-1]==0;dfs(a,b+1);         //右 
	} 
}

int main(void)                       //int main(void) 常规套路要记下来 
{
	int t;
	int n,m;
	cin>>t;
	while(t--)
	{
		int cnt=0;
		cin>>n>>m;
		for(int i=1;i<=n;i++)            //逐个输入二维数组的常规操作 
		{
			for(int j=0;j<=m;j++)
			{
				cin>>arr[i][j];
			}
		}
		
		for(int i=1;i<=n;i++)           //对二维数组进行遍历 
		{
			for(int j=1;j<=m;j++)
			{
				if(arr[i][j]==1)
				{
					cnt++;              //核心步骤 
					dfs(i,j);
				}
			}
		}
		
		cout<<cnt<<endl;
	}
	
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55

2、六角星问题

模型一：
六角星问题

题目：

如图【1.png】所示六角形中，填入1~12的数字。使得每条直线上的数字之和都相同。
图中，已经替你填好了3个数字，请你计算星号位置所代表的数字是多少？

在这里插入图片描述
本题小总结：

1、讲图中每一个节点抽象成一个数字，一共13个节点，用数组来存放其放的数字；
2、用v数组（visited）来表示一个数字是否被用过，如：
v[1]=1,即数字1已经被用过；
v[4]=0,即数字4未被用过。
如：

#include<bits/stdc++.h>
using namespace std;

int a[13]={0},v[13]={0};     //a是表示图的数组，v是表示某个数字是否使用过visited
void dfs(int x);
void jude(void);            //声明一下；

int main(void)
{
	int i;
	a[1]=1;
	a[2]=8;
	a[12]=3;                    //给图标号
	
	v[1]=1;
	v[8]=1;
	v[3]=1;                      //给使用过的数字mark一下； 
	
	dfs(1);
	return 0;
 } 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

3、若x是1，2，12这三个已经有了的，直接进行下一步dfs；
如果x是13，则进行判断；
前面有这两个if判断后，走到这一步的都是非1，2，12，13的，接下来是核心操作：
若数字未被用过，就直接把该数字放进去，然后一直向下递归（dfs(x+1)），到13后判断，如果不符合题意，就退回到dfs(x+1)的下一步，v[i]=0,即之前用过的那个数字行不通，不用那个数字，从那个数字之后往下尝试递归。
如下：

void dfs(int x)
 {
	int i,b[6];             //b代表六条边
	if(x==1||x==2||x==12)         //如果x是1，2，12这三个一开始已经有的，就直接递归到下一个； 
	{
		dfs(x+1);
		return ;
	}
	
	if(x==13)                     //如果x是13，最后一个，就进行判断； 
	{
		jude();
	}
	
	for(i=1;i<13;i++)           //核心操作：从数字1到12，如果有没有用过（v[数字]=0），就让它被用，放入下一个空格，然后反复调用 
	{
		if(v[i]==0)
		{
			v[i]=1;
			a[x]=i;
			dfs(x+1);
			v[i]=0;
		}
	}
 }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

4、这一步是定义判断函数，判断每条表之和是否相等。相当通俗易懂，直接放代码：

void jude(void)
 {
 	int i,b[6];
 	b[0]=a[1]+a[3]+a[6]+a[8]; 
	b[1]=a[1]+a[4]+a[7]+a[11];
	b[2]=a[2]+a[3]+a[4]+a[5];
	b[3]=a[2]+a[6]+a[9]+a[12];
	b[4]=a[5]+a[7]+a[10]+a[12];
	b[5]=a[8]+a[9]+a[10]+a[11];

	for(i=1;i<6;i++)
	{
		if(b[i]!=b[i-1])
		{
			return;
		}
	}
	cout<<a[6];
 }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

总体思想就是递归和回溯，加上数组的运用。
整体代码：

#include<bits/stdc++.h>
using namespace std;

int a[13]={0},v[13]={0};     //a是表示图的数组，v是表示某个数字是否使用过visited
void dfs(int x);
void jude(void);            //声明一下；

int main(void)
{
	int i;
	a[1]=1;
	a[2]=8;
	a[12]=3;                    //给图标号
	
	v[1]=1;
	v[8]=1;
	v[3]=1;                      //给使用过的数字mark一下； 
	
	dfs(1);
	return 0;
 } 
 
 void dfs(int x)
 {
	int i,b[6];             //b代表六条边
	if(x==1||x==2||x==12)         //如果x是1，2，12这三个一开始已经有的，就直接递归到下一个； 
	{
		dfs(x+1);
		return ;
	}
	
	if(x==13)                     //如果x是13，最后一个，就进行判断； 
	{
		jude();
	}
	
	for(i=1;i<13;i++)           //核心操作：从数字1到12，如果有没有用过（v[数字]=0），就让它被用，放入下一个空格，然后反复调用 
	{
		if(v[i]==0)
		{
			v[i]=1;
			a[x]=i;
			dfs(x+1);
			v[i]=0;
		}
	}
 }
 
 void jude(void)
 {
 	int i,b[6];
 	b[0]=a[1]+a[3]+a[6]+a[8]; 
	b[1]=a[1]+a[4]+a[7]+a[11];
	b[2]=a[2]+a[3]+a[4]+a[5];
	b[3]=a[2]+a[6]+a[9]+a[12];
	b[4]=a[5]+a[7]+a[10]+a[12];
	b[5]=a[8]+a[9]+a[10]+a[11];

	for(i=1;i<6;i++)
	{
		if(b[i]!=b[i-1])
		{
			return;
		}
	}
	cout<<a[6];
 }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67

3、N皇后问题

模型二

在N*N格的国际象棋上摆放N个皇后，使其不能互相攻击，
即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

如果出现x+y==某个常数，那么它们就在一条对角线上了。
+n是因为数组下标不能为负，加的一个参数而已。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10;
int n;
char g[N][N];
int lie[N],zdj[N],fdj[N];
void dfs(int u)//u是行 每行只能有一个 
{
	if(u==n)//结束
	{
		for(int i=0;i<n;i++) cout<<g[i]<<endl;
		cout<<endl;
		return;
	} 
	
	for(int i=0;i<n;i++)
	{
		if(!lie[i]&&!zdj[u+i]&&!fdj[n-u+i])
		{
			g[u][i]='Q';
			lie[i]=1;
			zdj[u+i]=1;fdj[n-u+i]=1;
			dfs(u+1);//下一行
			g[u][i]='.';//恢复现场 
			lie[i]=0;
			zdj[u+i]=0;fdj[n-u+i]=0;
		}
	}
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			g[i][j]='.';
		}
	}
	dfs(0);
	return 0; 
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

解法在这里：
一个模板。

4、带分数

100 可以表示为带分数的形式：100 = 3 + 69258 / 714 ， 还可以表示为：100 = 82 + 3546 / 197
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。
题目要求：
从标准输入读入一个正整数N (N<1000*1000)
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！

小总结：
1、主函数：输入、调用dfs函数，输出；
2、dfs函数，不断递归和某个数字是否使用等操作；
3、jude判断函数，调用sum函数组合出许多种数字组合并判断是否能符合题意；
4、sum函数，将传入的数字一个个组成如题所示的数字，如24567这种；

dfs函数里的注释：
若某个数字没有用过，则将它使用，并进入下一层递归，然后自然地就到了jude，若可以则count1++；
行或不行都回溯回来，重新用不同的数字，即v[i]=0,然后循环到下一个数字；

本题有两个坑点：
1、分母不能做除数，要进行判断；
2、可能报“reference to ’ *** ’ is ambiguous”的错，因为用的是万能头，我定义的变量名跟里面的属性或者方法重名了，将***里的变量名改一下即可。

整体代码：

#include<bits/stdc++.h>
using namespace std;

long long count1=0,p;
int a[10],v[10]={0};

void dfs(int n);                 //一堆声明； 
void jude(void);
int sum(int x,int y);

int main(void)
{
	cin>>p;
	dfs(1);
	cout<<count1;
	
	return 0;
}

void dfs(int n)
{
	int i;
	
	if(n>9)                  //当递归到9以上即数字都用完了，可以进行判断 
	{
		jude();
	}
	
	for(i=1;i<10;i++)           //反复递归 
	{
		if(!v[i])
		{
			v[i]=1;           //若某个数字没有用过，则将它使用，并进入下一层递归，然后自然地就到了jude，若可以则count1++； 
			a[n]=i;             //行或不行都回溯回来，重新用不同的数字，即v[i]=0,然后循环到下一个数字； 
			dfs(n+1);
			v[i]=0;
		}
	}
}

void jude(void)
{
	int x,y,z;
	
	for(int i=0;i<8;i++)
	{
		for(int j=i+1;j<9;j++)         //这个循环是步骤最多的地方；把每一种可能的数字组合都试了一遍； 
		{                                //且，数字可以不连续，因为某个数字若已经用过就跳过去了； 
			x=sum(1,i);
			y=sum(i+1,j);
			z=sum(j+1,9);
			
			if((p-x)*z==y)              //即题目中的分式等式 
			{
				count1++;
			}
		}
	}
}

int sum(int x,int y)
{
	int s=0;
	
	if(y==0)             //分母不能做除数 
	{
		return 0;
	}
	
	for(x;x<y;x++)
	{
		s=s*10+a[x];
	}
	
	return s;
 } 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76

关于经典例题的总结

摘自参见资料5

2-4题都有相同的一段代码：

这个函数做的就是把每一种情况列举一次，再用jude函数筛选。
这种模型适合的题目是：给你一个图让你填不重复的数。

void dfs(int n)
{
    int i;
    if(n>x)
    jude();
    for(i=1;i<=x;i++) 
        if(v[i])
        {
            v[i] = 0;
            a[n] = i;
            dfs(n+1); 
            v[i] = 1;
          } 
}  

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

其他题（链接）

AcWing 129. 火车进栈 dfs+栈

AcWing 129. 火车进栈 dfs+栈

飞行员兄弟 DFS+枚举

飞行员兄弟 DFS+枚举

Lake Counting(经典dfs)

Lake Counting

#include<iostream>
using namespace std;
typedef long long ll;
//======================
const int N=100+10;
char a[N][N];
int vis[N][N];
int ans=0;
int dx[8]={-1,0,1,-1,1,-1,0,1};
int dy[8]={-1,-1,-1,0,0,1,1,1};
int n,m;
void dfs(int x,int y)//坐标
{
	if(vis[x][y]) return;
	vis[x][y]=1;
	for(int i=0;i<8;i++)
	{
		int xx=x+dx[i];
		int yy=y+dy[i];
		
		if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]&&a[xx][yy]=='W')
		{					
			dfs(xx,yy);
		}
	}
} 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%s",a[i]+1);
	}

	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			if(!vis[i][j]&&a[i][j]=='W')
			{
				ans++;
			//	cout<<i<<" "<<j<<endl;
				dfs(i,j);
			}
		}
	
	cout<<ans;
	return 0; 
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

可参考资料

1、图的详解
2、较为全面的大佬博客
3、算法源码，用C++、C和Java
4、简单的水池问题
5、大佬的模型例题，好几道
6、非常厉害的入门模板
7、时隔很久的一点题目总结

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/596568
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号