搜索与图论——DFS与BFS

名称	数据结构	空间	特点
DFS深度优先搜索	staek	O(h)	不具有最短路
BFS宽度优先搜索	queue	O(2h)	最短路

2. DFS搜索顺序
深度优先搜索，每次总是搜索到一条路径上的最终子节点，然后开始回溯，搜索下一个分支节点。下图以三层树为例：
3. 例题1：全排列问题

给定一个从1开始长度为 n 的不包含重复数字的序列，请你求出其所有不重复的全排列。

输入格式
第一行包含整数 n。

输出格式
输出所有的不同排列，每种排列占一行。

在确定每种排列的输出顺序时，第一个数较小的先输出，第一个数相同时，第二个数较小的先输出，以此类推。

数据范围
1≤n≤9,
数组中包含的元素的取值范围 [1,9]
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

#include<iostream>

using namespace std;

const int N = 10;

int n;
int path[N];	// 存储每次搜索的路径，即每种情况对应的答案
bool st[N];		// 记录n个数是否被使用过，true为被使用过，false为未使用

// 函数功能：递归实现搜索
// 每一层递归相当于树的每一层，确定第i个空填几
void dfs(int u)
{
	// 递归终止条件：搜索到最后一层即最底层叶子节点
	if(u == n) // 如果递归的层数等于n则代表n个空全填满
	{
		for(int i = 0; i < n; i++) printf("%d ", path[i]);
		puts("");
		return;
	}

	// 判断该空应该填哪个未使用的数
	for(int i = 1; i <= n; i++)
		if(!st[i]) 
		{
			path[u] = i;
			st[i] = true;  // 标记已使用
			dfs(u + 1);		// 向下一层递归
			st[i] = false;	// 回溯，保留原状态
		}
}

int main()
{
	cin >> n;

	dfs(0);

	return 0;
}			

解题思路: 每一层递归在第i个空位中填一个未被使用的数，每次填到最后一个空位后开始回溯。

例题2：n皇后问题
n皇后问题是指将n个皇后放在n*n的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后不能处于同一行、同一列或同一斜线上。

现在给定整数n，请你输出所有的满足条件的棋子摆法。

输入格式
共一行，包含整数n。

输出格式
每个解决方案占n行，每行输出一个长度为n的字符串，用来表示完整的棋盘状态。
其中“.”表示一个位置的方格状态为空，“Q"表示某一个位置的方格上摆着皇后。
每个方案输出完成后，输出一个空行。

数据范围
1≤n≤9

输入示例：
4
输入示例：
…Q.
Q…
…Q
.Q…

.Q…
…Q
Q…
…Q.

解法一：以每一行递归的顺序搜索
#include<iostream>

using namespace std;

const int N = 20; 	// 开两倍大小，防止数组坐标为负

int n;
char g[N][N];	// 储存皇后的位置
bool col[N], dg[N], udg[N];	// 分别储存列，正对角线，反对角线上是否有皇后，true代表有，false代表没有

// 函数功能：递归求每一行皇后放置的位置
void dfs(int u)
{
	// 递归终止条件：搜索到最后一层即最底层叶子节点
	if(u == n) // 如果层数为n则输出
	{
		for(int i = 0; i < n; i++) puts(g[i]);
		puts("");
		return;
	}
	
	// 枚举每一列是否可以放皇后
	for(int i = 0; i < n; i++)
		if(!col[i] && !dg[u + i] && !udg[n - u + i])
		{
			g[u][i] = 'Q';
			col[i] = dg[u + i] = udg[n - u + i] = true;
			dfs(u + 1);
			col[i] = dg[u + i] = udg[n - u + i] = false;
			g[u][i] = '.';
		}
}

int main()
{
	cin >> n;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j ++)
			g[i][j] = '.';

	dfs(0);

	return 0;
}		

解题思路：因为每一行只能有一个皇后，所以只用判断每一层的皇后放在第几列就可以。这与例1的思路一样。

解法二：以每一个格子为顺序搜索
#include<iostream>

using namespace std;

const int N = 20; 	// 开两倍大小，防止数组坐标为负

int n;
char g[N][N];	// 储存皇后的位置
bool row[N], col[N], dg[N], udg[N];	// 分别储存列，正对角线，反对角线上是否有皇后，true代表有，false代表没有

// 函数功能：递归求每一行皇后放置的位置
void dfs(int x, int y, int s)
{
	if(y == n) y = 0, x++;

	if(x == n)
	{
		if(s == n)
		{
			for(int i = 0; i < n; i++) puts(g[i]);
			puts("");
		}
		return;
	}

	// 不放皇后
	if(!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
	{
		g[x][y] = 'Q';
		row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
		dfs(x, y + 1, s+1);
		row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
		g[x][y] = '.';
	}			
}

int main()
{
	cin >> n;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j ++)
			g[i][j] = '.';

	dfs(0, 0, 0);

	return 0;
}