深度优先搜索DFS详解(+例题,超详细)_深度优先搜索例题

什么是深度优先搜索

深度优先搜索(depth first search，简称DFS)是一种遍历算法，是对于每一个分支一个分支进行到底再进行另一个分支的算法，用一张图来表示。
(圈圈上的数是遍历顺序)

深度优先搜索能解决什么

深度优先搜索能解决连通块，迷宫类，地图类，病毒传染类等问题。

信息学奥赛一本通，1216：红与黑

（1216：红与黑）
【题目描述】
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。
【输入】
包括多组数据。每组数据的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下:
1）‘.’：黑色的瓷砖；
2）‘#’：红色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每组数据中唯一出现一次。
当在一行中读入的是两个零时，表示输入结束。
【输出】
对每组数据，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
【输入样例】

6 9 
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0
1
2
3
4
5
6
7
8
9
10
11

【输出样例】
45

这题从@的位置开始遍历，对于每一个方格，找到它的相邻位置，判断是否为黑瓷砖，如果是，那就把这个瓷砖作为新起点，每遍历一格，就把这个瓷砖设为红瓷砖（防止重复），并将个数加一。

信息学奥赛一本通，1329：【例8.2】细胞

（1329：【例8.2】细胞）
【题目描述】
一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如:

4 10
0234500067
1034560500
2045600671
0000000089
1
2
3
4
5

有4个细胞。
【输入】
第一行为矩阵的行n和列m;
下面为一个n×m的矩阵。
【输出】
细胞个数。
【输入样例】

4 10
0234500067
1034560500
2045600671
0000000089
1
2
3
4
5

【输出样例】
4

这题是求连通块的个数，首先遍历每一格，看它是不是细胞，若是，就用深度优先搜索遍历这个细胞（为了不重复，将遍历过的细胞设为0），然后遍历完之后，个数加一。

函数代码实现

那么如何用好代码实现呢？我们可以用递归。
第一步定义数组dx和dy，用于移动（增加坐标）

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

这两个数组需要配合着用，比如第一种移动方向，$x=+0(dx[0]),y=-1(dy[0])$,表示x坐标不变，y坐标-1
注意：这是上下左右，如果题目说可以斜着走，那么还要有斜着走的项目

第二步定义递归函数dfs

void dfs(int x,int y)
{
	
}
1
2
3
4

第三步将当前坐标$(x,y)$设为遍历过状态。

a[x][y]=0;
1

注意：这里a数组是bool类型，若为其他类型，需要随机应变

第四步遍历周围格，并判断是否为遍历过状态，是否出界

for(int i = 0; i < 4; i++)
{
	int xx=x+dx[i],yy=y+dy[i];
	if(a[xx][yy]&&xx>0&&xx<=n&&yy>0&&yy<m)//a数组是bool类型
	{
		
	}
}
1
2
3
4
5
6
7
8

第五步递归遍历

dfs(xx,yy);
1

函数完整代码

int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
void dfs(int x,int y)
{
	a[x][y]=0;
	for(int i = 0; i < 4; i++)
	{
		int xx=x+dx[i],yy=y+dy[i];
		if(a[xx][yy])
		{
			dfs(xx,yy);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

例题

红与黑

题目见上方

#include<stdio.h>
#include<iostream>
using namespace std;
int n , m;
int ans = 0;
char a[40][40];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
void dfs(int x, int y)
{
	a[xx][yy] = '#';
	for(int i = 0 ; i < 4 ; i++)
	{
		int xx = x + dx[i];
		int yy = y + dy[i];
		if(xx >= 0 && xx < n && yy >= 0 && yy < m && a[xx][yy] == '.') 
		{
			ans++;//这里要将答案加一
			dfs(xx,yy);
		} 
	}
}
int main()
{
	while(cin>> m >> n && n+m > 0)
	{
		ans = 1;
		int sx,sy;
		for(int i = 0 ; i < n ; i++)
		{
			cin >> a[i];
			for(int j = 0 ;j  < m ; j++)
				if(a[i][j] == '@')
					sx  = i , sy = j;
		}
		dfs(sx,sy);
		cout<<ans<<endl;
	}
}
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

细胞

题目见上方

#include <iostream>
int n,m;
int a[105][105];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
void dfs(int ,x,int y)
{
	a[x][y]=0;
	for(int i = 0; i < 4; i++)
	{
		int xx= x+dx[i],yy=y+dy[i];
		if(xx>0&&yy>0&&xx<=n&&yy<=m&&a[xx][yy]>0)
		{
			dfs(xx,yy);
		}
	}
}
int main()
{
	int ans=0;
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> a[i][j];
	for(int i = 1;i <= n; i++)
	{
		for(int j = 1; j <= m; j++)
		{
			if(a[i][j]>0）
			{
				dfs(i,j);
				ans++;
			}
		}
	}
	cout << ans;
}
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