数据结构_dfs深度优先算法入门（C语言）_dfs算法c语言

数据结构_dfs深度优先算法入门（C语言）

0.闲话

​ 才学习数据结构的dfs，做一下笔记记录一下，加深理解-.-

​ 我这里就简单讲一下我的理解和一下例子

​ 推荐学习资源（B站视频，原理和实例）：

洛谷 普及组( CSP - J )试炼场 - 深度优先搜索 （DFS)

​ 编译环境：vc++6.0

1.个人理解

dfs，名叫深度优先搜索，就是从一个节点一直往深处搜索，直到走到尽头，再往回走，走下一个节点，再次深搜……就相当于来回遍历，一个人走迷宫。

所以，dfs是运用递归的方法，基于回溯的思想。而回溯就是基于栈结构。

栈结构的话，直接用数组来实现就可以了。

重点：C代码一定要从main函数开始看。

2.全排列问题（1到n的排列组合）

​ 全排列问题的一个重点：比如走迷宫一样，最开始有个起始点，下一步有多个选择。当我们要深搜时，如果没有一个固定的起始点，我们要假想构造一个0起始点，从0起始点开始往下走选择。以此来构造一个有规律可递归的函数。

#include<stdio.h>
#define N 20
int n;//将其设置为全局变量
int visit[N]={0};//0代表未访问，1代表已访问。
int a[N] = {0};//记录全排列的方式。

//输出函数
void printF()
{
	int i ;
	for(i=1 ; i<=n ; i++)
		printf("%5d",a[i]);
	printf("\n");
}

void dfs(int x)//x代表递归的层数
{
	int i;
	if(x>n)
		printF();//输出一种结果
	
	for(i=1 ; i<=n ; i++)//递归时，每层都有循环
	{
		if(!visit[i])//i这个数是否排过序。
		{
			visit[i] = 1;//代表排过序
			a[x] = i;//记录i
			
			dfs(x+1);//进入下一层递归
			
			//回溯，归零。
			visit[i] = 0;
			a[x] = 0;//这一步可以不写
		}
	}	
}

int main()
{

	printf("Please input n:");
	scanf("%d",&n);

	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
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

2.八皇后问题求解

简述规则就是，每行每列每个斜对角线只能站一个皇后，斜对角线包括左上到右下，和左下到右上，两种。

其实也是在全排列的基础上，加上八皇后特有的条件，进行递归。

#include<stdio.h>
#define N 20
	
int n;

int u[2*N] = {0};//右上到左下，防止皇后在同一斜对角线。
int v[2*N] = {0};//左上到右下，1代表斜对角线有皇后，0代表没有。

int list[N] = {0};//记录同一列
int a[N] = {0};//记录皇后的位置
int sum = 0;//记录解法

void printF()//将得到的结果输出
{
	int i;	
	for( i=1 ; i<=n ; i++)
		printf("%2d",a[i]);
	putchar('\n');
}

void dfs(int x)
{	
	int i,j;

	if( x>n )
	{	
		sum++;
		printF();//将一种结果输出
		return ;
	}
	for(i=1 ; i<=n ; i++)//代表每行
	{
		if(list[i]==0 && u[x+i]==0 && v[x-i+n]==0)
		{
			//置一，代表这些位置不能再放皇后
			list[i] = 1;
			u[x+i] = 1;
			v[x-i+n] = 1;//防止相减后是负数，同一所有加个n。
			
			a[x] = i;//记录这个位置，x代表行，i代表列。

			dfs(x+1);

			//回溯，相当于栈结构
			list[i] = 0;
			u[x+i] = 0;
			v[x-i+N] = 0;
			a[x] = 0;
		}		
	}
}	
	
int main()
{	
	printf("Please input n: ");//n皇后
	scanf("%d",&n);
	dfs(1);
	printf("There are %d sulutions!\n",sum);
	
}
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

3.二维迷宫

​ 输入：

​ 输入规则：

1. 第一行输入行n、列m、障碍个数t
2. 第二行分别输入起始坐标sx、sy和终点坐标fx、fy
3. 第三行即后面依次每行输入一个障碍坐标，（根据输入的障碍个数）。

（1）只输走出迷宫解的个数

//三、二维迷宫求解:求解的个数。
#include<stdio.h>
#define N 20

int n,m,t;//行、列、障碍个数
int sx,sy,fx,fy;//起始位置，终点位置。

int map[N][N] = {0};//标记障碍。
int visit[N][N] = {0};//标记是否走过。

int xx[] = {1,0,-1,0};
int yy[] = {0,1,0,-1};

int sum = 0; //记录总数。

void dfs(int x,int y)
{
	int i;
	int dx,dy;//记录下一步的位置。
	if(x==fx && y==fy)
		sum++;


	for(i=0 ; i<4 ; i++)
	{
		dx = xx[i] + x;
		dy = yy[i] + y;
		
		if(dx>=1 && dx<=n && dy>=1 && dy<=m && !map[dx][dy] && !visit[dx][dy])
		{
			visit[dx][dy] = 1;
			
			dfs(dx,dy);
			
			visit[dx][dy] = 0;
		}
	}
}


int main()
{
	int x,y;//记录障碍位置。
	printf("Please input : \n");
	scanf("%d%d%d",&n,&m,&t);//输入行、列、障碍个数
	scanf("%d%d%d%d",&sx,&sy,&fx,&fy);//数去起始坐标和终点坐标
	while(t--)
	{
		scanf("%d%d",&x,&y);
		map[x][y] = 1;//标记障碍坐标
	}
	
	visit[sx][sy] = 1;
	
	dfs(sx,sy);//从起点位置开始递归。

	printf("There are %d solution!\n",sum);
	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
56
57
58
59
60

（2）输出解的个数和路径

#include<stdio.h>
#define N 20

int n,m,t;//n为行，m为列，t为障碍数。
int sx,sy;//起点坐标。
int fx,fy;//终点坐标。
int map[N][N] = {0};//地图，标记障碍。
int visit[N][N] = {0};//记录是否走过。

char a[N*N] = {0};//记录上下左右。
int sum = 0;//记录路径总数。

//输出函数，每次输出路径和增加解的个数
void printF(int k)
{
	int i;
	for(i=1 ; i<=k ; i++)
		printf("%c",a[i]);

	printf("\n");
	sum++;
}
//x、y代表此时的位置，k代表走到第几步，方便记录路径。
void dfs(int x, int y, int k)
{
	int i;
	int dx,dy;//记录当前位置。

	if(x==fx && y==fy)//走出迷宫输出输出路径
	{
		printF( k-1 );
		return;
	}
	for(i=0 ; i<4 ; i++)//只有四种走法，上下左右。
	{	
		//如果不满足则for循环回到这一层函数开始的坐标位置
		dx = x;//这也是回溯，
		dy = y;//这也是回溯
		
		switch (i)
		{
			case 0:
				dx++;
				a[k] = 's';//上
				break;
			case 1:
				dy++;
				a[k] = 'y';//右
				break;
			case 2:
				dx--;
				a[k] = 'x';//下
				break;
			case 3:
				dy--;
				a[k] = 'z';//左
				break;					
		}
		if(dx>=1 && dx<=n && dy>=1 && dy<=m && !visit[dx][dy] && !map[dx][dy])//所有条件
		{
			visit[dx][dy] = 1;//标记走过

			dfs(dx,dy,k+1);//进入下一层递归

			visit[dx][dy] = 0;//回溯
		}
	}
}


//所有的x都代表行数，y代表列数。
int main()
{
	int i;
	int x,y;//记录障碍点。
	printf("Please input : \n");
	scanf("%d%d%d",&n,&m,&t);//输入行、列、障碍个数
	scanf("%d%d%d%d",&sx,&sy,&fx,&fy);//数去起始坐标和终点坐标
	while(t--)//循环输入障碍坐标
	{
		scanf("%d%d",&x,&y);
		map[x][y] = 1;//标记障碍坐标
	}
	
	visit[sx][sy] = 1;//代表第一步已走。
	dfs(sx,sy,1);//从起点位置开始递归。1代表第一步
	
	printf("There are %d solutions!\n",sum);

	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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

---

欢迎大家留言交流0.0