【数据结构与算法】—— * 深度优先搜索入门 *_深度优先搜索扑克牌

问题引入

输入一个数n，输出1~n的全排列

问题解析

假设有编号为1,2,3的3张扑克牌和编号为1,2,3的3个盒子。需要将这3张扑克牌分别放到3个盒子里面，并且每个盒子有且只能放一张扑克牌。问一共有多少种放法？

首先，我们按照正常的顺序来进行放置，顺序为——“1-2-3”

然后我们走到了第四个盒子前，这时候已经没有扑克牌可以放置了，现在我们要重新回到3号盒子前，需要取回之前放在3号盒子里的扑克牌，再去尝试看看能不能放别的扑克牌，从而产生一个新的排列。于是我们取回3号扑克牌。 

但这时候我们发现手中仍然只有3号扑克牌，没有别的选择，我们不得不回到2号盒子前收回2号扑克。现在我们手里有2张扑克牌，分别是2,3.按照之前约定的顺序（每次到一个盒子前，先放1号，再放2号，最后放3号）我们需要往2号盒子里面放3号扑克牌（上一次放的是2号扑克牌）。放好后来到三号盒子前，将手中仅剩的2号扑克牌放入3号盒子中，又来到了4号盒子面前（不存在），这时候产生了新的排列——“1.3.2”

按照这样的步骤去模拟，我们便会产生所有的排列

 问题解决

最基本的问题：放入扑克牌 

for(i = 1;i <= n;i++)
{
    if(book[i] == 0)
    {
    a[step] = i;    //book[i] 等于0表示第i号扑克还在手上
    book[i] = 1;    //表明book[i]已经不在手上
    }
}

使用book数组来标记哪些数组已经使用了

将这串代码封装成一个函数，用同样的方式去处理step+1个盒子

void dfs(int step)   //step表示现在站在第几个盒子前面
{
 
	//处理第step个小盒子
	for (i = 1; i <= n; i++)
	{
		if (book[i] == 0)  //book[i] 等于0表示第i号扑克还在手上
		{
			a[step] = i;	//将第i号扑克放入第step个盒子中
			book[i] = 1;	//表明book[i]已经不在手上
		}
	}
	return;
}

处理第step+1个小盒子的方法就是dfs（step+1）

void dfs(int step)   //step表示现在站在第几个盒子前面
{
 
	//处理第step个小盒子
	for (i = 1; i <= n; i++)
	{
		if (book[i] == 0)  //book[i] 等于0表示第i号扑克还在手上
		{
			a[step] = i;	//将第i号扑克放入第step个盒子中
			book[i] = 1;	//表明book[i]已经不在手上
			dfs(step + 1);	//这里用函数递归的调用来实现（自己调用自己）
			book[i] = 0;	//这是非常重要的一步，一定要将刚才尝试的扑克牌收回，才能进行下一步尝试
			//如果不把刚才放入小盒子的扑克牌收回，那将无法再进行下一步的摆放
			//当step = n + 1时，表明前n个盒子都已经放好扑克了
		}
	}
	return;
}

上面代码中的 book[i] = 0 这条语句非常重要，这句话的作用是将小盒子中的扑克牌收回，因为在一次摆放尝试结束返回的时候，如果不把刚才放入小盒子中的扑克牌收回，那将无法进行下一次摆放。

当我们处理到第n+1个盒子的时候，证明我们前n个已经排序完毕，将他们打印出来即可。

打印完毕一定要return，否则会无休止地运行下去。

完整代码 

//深度优先搜索
 
int a[10], book[10], n;
//C语言的全局变量在没有赋值以前默认为0
//因此这里的book数组无需再全部赋值初始值0
 
//将放牌封装成一个函数
void dfs(int step)   //step表示现在站在第几个盒子前面
{
	int i;
	if (step == n + 1)		//如果站在第n+1个盒子前，表明前n个盒子都已经完成了放置
	{
		//输出一种排列
		for (i = 1; i <= n; i++)
			printf("%d", a[i]);	
		printf("\n");
		return;   //返回之前最近的一步（最近一次调用dfs的地方）
		//打印完要立即return，否则会无限循环下去
	}
	//处理第step个小盒子
	for (i = 1; i <= n; i++)
	{
		if (book[i] == 0)  //book[i] 等于0表示第i号扑克还在手上
		{
			a[step] = i;	//将第i号扑克放入第step个盒子中
			book[i] = 1;	//表明book[i]已经不在手上
			dfs(step + 1);	//这里用函数递归的调用来实现（自己调用自己）
			book[i] = 0;	//这是非常重要的一步，一定要将刚才尝试的扑克牌收回，才能进行下一步尝试
			//如果不把刚才放入小盒子的扑克牌收回，那将无法再进行下一步的摆放
			//当step = n + 1时，表明前n个盒子都已经放好扑克了
		}
	}
	return;
}
 
int main()
{
	scanf("%d", &n);	//输入时要注意为1-9之间的整数
	dfs(1);	//首先站在1号小盒面前
	return 0;
}

总结 

深度优先搜索（Depth First Search,DFS）

理解深度优先搜索的关键在于解决“当下该如何做”。至于“下一步该如何做”，则与“当下该如何做”是一样的。

基本模型

void dfs(int step)
{
    判断边界
    尝试每一种可能
    for(i = 1;i <= n;i++)
    {
    继续下一步的尝试 dfs（step+1）
    }
    返回
}

每一种尝试就是一种“扩展”。每次站在一个盒子前面的时候，都有n种扩展方法，但不是每一种方法都能够成功扩展。

这就是今天的全部内容啦，如果觉得有帮助，请