深度优先搜索题目（DFS）

简单介绍：

DFS，是一种常用的图遍历算法，用于在图或树数据结构中遍历所有节点。沿着一条路径尽可能的深入，无法深入时便会返回。

深度优先搜索（DFS）的优点：

1. 空间复杂度较低：DFS不需要保存所有节点的信息，只需要保存当前节点的路径信息，因此空间复杂度较低。
2. 可以找到所有解决方案：对于某些问题，DFS可以找出所有可能的解决方案。

深度优先搜索（DFS）的缺点：

1. 时间复杂度较高：DFS需要遍历所有可能的路径，因此时间复杂度较高。
2. 可能产生回溯：在DFS中，如果当前路径不可行，需要回溯到上一个节点重新选择路径，这会增加算法的复杂性。

DFS可能更适用于求解图的连通性、寻找图的路径等问题中。

区别：

深度优先搜索不保证找到最短路径。因为它首先沿着一条路径尽可能远地深入。如果需要找到最短路径，可以考虑使用其他算法，如广度优先搜索（BFS）。一般最小步数、最短距离、最小操作次数等问题采用BFS。思路奇怪或是对空间要求高的使用深度优先搜索（DFS）。

题目一（全排列问题）：

代码加详细解析：

#include<stdio.h>//深度优先搜索
int a[15], g[15], n;//a数组存放输出，g数组用来标记是否已经存放该数组
void print()//打印
{
	for (int i = 0; i < n; i++) {//打印排列成一行的数
		printf("%5d", a[i]);//题目要求宽度，所以在%和d之间放了5
	}
	printf("\n");//换行
}
void dfs(int step)//相当于步数，每存一个数走一步
{
	if (step == n) {//当step=n时，说明已经排列成一行
		print();//调用函数，被调用的函数应该dfs函数要放在前面，否则在这个dfs函数内要重新定义一遍。
		return;
	}
	for (int i = 1; i <= n; i++) {//存数
		if (g[i] == 0) {//当这个数没有被存放时进入
			g[i] = 1;//标记
			a[step] = i;
			dfs(step + 1);//递归
			g[i] = 0;//解除标记
		}
	}
	return;
}
int main()
{
	scanf("%d", &n);
	dfs(0);
	return 0;
}

题目二（自然数的拆分问题）：

代码加详细解析：

#include<stdio.h>
int g[20], n;//拆分下来的数用数组存着
void print(int m)//拆下来的数的个数
{
//分开写是因为有+号要放进去
	printf("%d", g[0]);
	for (int i = 1; i < m; i++) {
		printf("+%d", g[i]);
	}
	printf("\n");//输出完一个式子要换行
	return;
}
void dfs(int a, int b, int c) //a为待相加的数字，b为拆开数字之和，c为拆开的个数
{
 
	if (a == n)return;//没有这种情况
	if (b == n) {//如果相加数字之和等于输入的数字
		print(c);//输出
		return;//结束
	}
	for (int i = a; i <= n-b; i++) {//从a开始相加，i=n-b这是剩下的数量
		g[c] = i;//存放入数组
		dfs(i, b + i, c + 1);//b+i表示和，c+1表示拆下来的个数
	}
	return;
}
int main()
{
	scanf("%d", &n);//输入个数
	dfs(1, 0, 0);//从1开始相加，初始拆开数字之和为0，拆开的个数也为0
	return 0;
}

题目三（高手去散步）：

代码加详细解析：

#include<stdio.h>
int max = -1;//定义到最外面，保证max可以及时发生改变
int n, m;//n为景点个数，m为道路
int next[25][25], book[25];//next表示可以行动的路径
void bfs(int s,int count,int p)//s为当前走过的路径，count为当前走过的景点，p为当前位置
{
	if (s > max)max = s;//最长路径
	if (count == n)return;//当count=n时，就说明景点都走到了
	for (int i = 1; i <= n; i++) {//next[p][i]从p到i
		if (next[p][i] > 0 && book[i] == 0) {
			book[i] = 1;//标记该景点已经走过
			bfs(s + next[p][i], count++, i);//s+next走过的路，count++,位置发生改变
			book[i] = 0;//取消标记
		}
	}
}
int main()
{
	int x, y, z;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &x, &y, &z);
		next[x][y] = z;//路径是双向的，所以有两种情况
		next[y][x] = z;
	}
	for (int i = 1; i <= n; i++) {
		book[i] = 1;//可以从任意位置开始
		bfs(0, 0, i);
		book[i] = 0;
		//清空用过的标记数组可以用
		//memset(book,0,sizeof(b));
	}
	printf("%d", max);//输出
	return 0;
}

题目四（八皇后）：

代码加解析： 

//八皇后
#include<stdio.h>
int n,p1;//p1就表示解的总数
//pow为行  c为列  p为对角线  q为对角线
int pow[100], c[100], p[100], q[100];
void print()
{
	//前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
	if (p1 <= 3) {
		for (int i = 1; i <= n; i++)printf("%d ", pow[i]);
		printf("\n");
	}
}
void dfs(int m) {//当前放皇后的行
	if (m > n) {
		p1++;//数量加一
		print();//进入打印环节
		return;
	}
	for (int j = 1; j <= n; j++) {
		if (c[j] == 1 || p[m + j] == 1 || q[m - j + n] == 1)continue;
		pow[m] = j;//记录皇后的位置
		c[j] = 1; p[m + j] = 1; q[m - j + n] = 1;//标记行列，对角线
		dfs(m + 1);
		c[j] = 0; p[m + j] = 0; q[m - j + n] = 0;//取消标记
	}
}
int main()
{
	scanf("%d", &n);
	dfs(1);
	printf("%d", p1);
	return 0;
}