深度优先搜索(DFS)

目录

简介

流程

例题

全排列

---

预计阅读时间：20分钟

简介

        深度优先搜索(Depth First Search)，是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链
走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。

流程

✓访问顶点v；

✓依次从v的未被访问的邻接点出发，对图进行深度优先搜索；直至图中和v有路径相通的顶点都被访问；

✓若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。　当然，当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫.事实上我们还有别的方法，那就是广度优先搜索(BFS)，广度优先搜索适合解决求最短路径这类题目。

例题

全排列

题目描述
假如有编号为1、2、3……n的n张扑克牌和编号为1、2、3……n的n个盒子。现在需要将这n张扑克牌分别放到n个盒子里面，并且每个盒子有且只能放一张扑克牌。那么一共有多少种不同的放法呢？

输入INPUT：

输入格式

输入一个正整数n（n≤9）

输入样例

3

输出OUTPUT：

输出格式

按字典序输出1~n的全排列。

输出样例

1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

题目分析：

♜首先走到1号盒子面前

♜先放1号扑克牌，还是先放2号扑克牌，还是先放3号扑克牌呢？

        ♛现在要生成的是全排列，很显然这三种情况都要去尝试

♜约定一个顺序：

        ♛每次到一个盒子面前时，都先放1号，再放2号，最后放3号扑克牌。

♜第一步将1号扑克牌放到第1个盒子中。    

过程如上图所示。

参考代码：

#include 
 
using namespace std;
int n,temp,i;
int a[10];//a是记录放置数字的顺序
bool v[15];//v表示该数字有没有放置
void dfs(int x)
{
	if(x==n+1)//输出a数组
	{
		for(int i=1; i<=n; i++)
		{
			cout<" ";
		}
		cout<<'\n';//这里不能用endl，用endl会超时
		return;
	}
	for(int i=1; i<=n; i++)//这里把每一个都遍历一遍
	{
		if(v[i]==0)
		{
			a[x]=i;//记下当前数字
			v[i]=1;//把当前的数标记为已放置
			dfs(x+1);//放下一个数字
			v[i]=0;//把当前的数标记为未放置
		}
	}
}
int main(int argc, char *argv[]) {
	cin>>n;
	dfs(1);
	return 0;
}

感谢阅读！