dfs(深度优先搜索)基本模型-c语言

dfs(深度优先搜索)基本模型-c语言 dfs的解决问题的思路：

先解决当下该如何做。然后再考虑下一步如何做。

问题：

输入一个数n，输出1~n的全排列。 分析：

形象化问题：

​ 假如有编号为1，2，3的三张扑克牌和编号为1，2，3的三个盒子。

​ 现在需要将3张扑克牌分别放到3个盒子里，每个盒子只能放一张。

约定一个顺序：每当需要输出一个数时，总是先输出1，然后是2，其次是3。 代码实现：

#include 
int a[10], book[10], n;//c语言的全局变量在没有赋值以前默认值是0  ！

void dfs(int step) {//step表示第几个盒子
	int i;//一定要定义在内部，不能定义为全局变量，因为要在内部使用。
	if (step == n + 1) {//如果没盒子了
		for (i = 1; i <= n; i++) {
			printf("%d ", a[i]);
			
		}
		printf("n");
		return;//表示返回上一步！！
	}
	for (i = 1; i <= n; i++) {
		if (book[i] == 0) {//如果牌i还在的话
		a[step] = i;//将i扑克牌放在第step个盒子里
		book[i] = 1;//给牌i做标记，标记已经用过了
		dfs(step + 1);//下一个盒子
		book[i] = 0;//将刚才尝试的扑克牌收回，然后再进行下一次
		
		}
		
		
	}
	
	return;
}
int main() {
	
	printf("请输入有几个数：");
	scanf_s("%d ", &n);
	
	dfs(1);//首先站在1号盒子前
	
	getchar(); getchar();
	return 0;
}

总结：

dfs–先解决第一步怎么办，第二步就是重复第一步即可。