DFS深度优先搜索和BFS深度优先搜索

DFS深度优先搜索

栈实现
空间o(h)
不具有最短路性质
演示图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Void DFS(deep,...){
if(找到解 || 走不下去了){
......//根据题意添加
return;
}

//for循环遍历每一种情况,例如:每一列都可能出现;1,2,3,4···每一个数字都可能出现
//对这些可能出现的进行for循环遍历
for(扩展方式){
if(扩展方式所能达到的状态合法){
修改操作;//根据题意添加
标记;
DFS(deep+1,...);
//根据题意是否要还原
}
}

}

例题

排列组合

20220115153422

八皇后

n-皇后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>

using namespace std;

const int N = 20;

int n;
char g[N][N];
bool col[N],dg[N],udg[N];//记录是否用过,列,正反对角线

inline void dfs(int u)
{

if(u==n)
{
for(int i=0;i<n;i++) puts(g[i]);
puts("");
return;
}
for(int i=0;i<n;i++)//遍历该层的每一种情况,一共n列 n种情况
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;
}

BFS深度优先搜索

队列实现
空间o(2^h)
最短路

演示图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void BFS(){
初始化队列Q;
起点S入队;
标记S已经访问;
while(Q非空){
取Q的队首元素U;
U出队列;
if(u==目标状态){
返回结果;
}
for(所有与U相邻的元素){
if(相邻的元素合法 && 未访问){
入队;
标记访问;
}
}
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
typedef pair<int, int> PII;
queue<PII> q;

const int N = 110;
int g[N][N];
int d[N][N]; //存放各个点到起点的距离(最短)

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;

int bfs()
{
memset(d, -1, sizeof d);//初始距离全部设置为-1 表示该点未被访问过(记录距离的同时,起到了st数组的作用)
q.push({0, 0});
d[0][0] = 0;

while(q.size())
{
auto t = q.front();
q.pop();

for(int i = 0; i < 4; i ++)
{
int a = t.first + dx[i], b = t.second + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;//越界
if(g[a][b]) continue;//撞墙
if(d[a][b] != -1) continue;//该点被访问过

q.push({a, b});
d[a][b] = d[t.first][t.second] + 1;//更新距离

}
}

//返回到终点的最短距离
return d[n - 1][m - 1];
}