前言
BFS、DFS这两个搜索算法都是对图的遍历,从图中某点出发,按照某种方法对图的所有顶点进行访问,每个点仅访问一次。
因为图对于树而言相对复杂,其中的任意顶点都可能与其他顶点相邻,所以在图的遍历中必须记录已经被访问过的点。
根据搜索路径的不同,我们可以将遍历图的方法分为两种:广度优先搜索和深度优先搜索。
实现bfs和dfs都需要解决的一个问题就是如何存储图。一般有两种方法:邻接矩阵和邻接表。这里为简单起
见,均采用邻接矩阵存储,说白了也就是二维数组。
实例
我的眼镜掉在了以我为中心边长为5的一块矩阵,现在我要找我的眼镜,假设每次都可以搜索前后左右的任意一个方向,我每次下手找都可以搜索目标方向边长为1的面积,下面我用DFS、和BFS两种方法找我的眼镜…
DFS算法
思想: 一直往深处走,知道找到解或者走不下去为止
因为我每次找眼镜都会按前后左右来判断时候符合需要搜索的条件,所以当我没有找到眼镜,并且下次要找的点没有超过边界时,会一直向前搜索,到头发现没有找到眼镜,返回一步后,因为前这个方向我已经找过了,我有了后左右,当然我不会傻到找我找过的地方,只剩了左右两个方向,判断左,符合条件,找左方向,进入那个点后,又有前后左右四个方向,继续判断…直到找到眼镜或者所有地方都走过了~~~~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17DFS(int x, int y) //这里假设存的是二维数组,x、y表示两个坐标 { if (找到解) { } for (......) //每到一个点下一步都有上下左右四个方向可以走,这里用一个循环遍历方向数组表示四个方向 { // 如果这个点(a,b)符合要求并且没走过 flag[a][b] = 1; //标记‘1’表示走过 DFS(a, b); //进入下一次递归 flag[a][b] = 0; //回溯,标记‘0’表示可以走 } } }
关于回溯 flag[a][b] = 0; //回溯
假如DFS每次都是按上下左右这个顺序判断是否能走,上走过了,每次都走下这个方向,最后发现走到了死胡同,而每次都标记了走过的坐标,就会导致无法退回去访问进入其他的点
而我们把“ flag[a][b] = 0; //回溯”放在了进入递归的下边,当走入了死胡同往回退的时候,每次出来都把上个点取消标记,仔细想一下,死胡同的这个点因为标记过不会再次进入了
框架
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
33bool vst[maxn][maxn]; // 访问标记 int map[maxn][maxn]; // 坐标范围 int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0}; // 方向向量,(x,y)周围的四个方向 bool CheckEdge(int x, int y) // 边界条件和约束条件的判断 { if (!vst[x][y] && ...) // 满足条件 return 1; else // 与约束条件冲突 return 0; } void dfs(int x, int y) { vst[x][y] = 1; // 标记该节点被访问过 if (map[x][y] == G) // 出现目标态G { ...... // 做相应处理 return; } for (int i = 0; i < 4; i++) { if (CheckEdge(x + dir[i][0], y + dir[i][1])) // 按照规则生成下一个节点 dfs(x + dir[i][0], y + dir[i][1]); } return; // 没有下层搜索节点,回溯 } int main() { ...... return 0; }
模板题1
模板题2
BFS算法
思想:广度优先搜索类似于树的层次遍历过程。它需要借助一个队列来实现。
不了解队列的同学可以看一下我写的这篇博客 STL模板库
我的眼镜又掉到了地上,怎么办呢,找呗~
依然是上面那种情况,这次我会把前后左右四个方向的点一次判断,如果符合要找的条件(没有找过,没有超界)就把它放进一个队列当中,下面开始循环,访问队列中的队首元素,对其上下左右四个点一次访问,判断时候符合需要找的条件,如果符合,把符合的这几个点放进队列的后面,对队首的四个方向判断完后就把它出队,当然我还需要标记一下我找过的地方,毕竟年纪大了记性比较差,下面我又访问队列中的队首,判断完后把符合条件的点加到队列中,再把这个队首出队…直到队列访问完了,找遍了所有的点或者是我找到了我的眼镜…结束
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19BFS() { queue<int> q;//初始化队列Q while(!q.empty()) //队列不为空 { if() //判断是否找到了目标 { } //队首出队 for() { //依旧是四个方向 //符合条件的入队 //标记入队的点 } } }
框架
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
45
46
47
48
49
50
51
52
53
54bool vst[maxn][maxn]; // 访问标记 int dir[4][2]={0,1,0,-1,1,0,-1,0}; // 方向向量 struct State // BFS 队列中的状态数据结构 { int x,y; // 坐标位置 int Step_Counter; // 搜索步数统计器 }; bool CheckState(State s) // 约束条件检验 { if(!vst[s.x][s.y] && ...) // 满足条件 return 1; else // 约束条件冲突 return 0; } void bfs(State st) { queue<State> q; // BFS 队列 State now, next; // 定义2 个状态,当前和下一个 st.Step_Counter = 0; // 计数器清零 q.push(st); // 入队 vst[st.x][st.y] = 1; // 访问标记 while (!q.empty()) { now = q.front(); // 取队首元素进行扩展 if (now == G) // 出现目标态,此时为Step_Counter 的最小值,可以退出即可 { ...... // 做相关处理 return; } for (int i = 0; i < 4; i++) { next.x = now.x + dir[i][0]; // 按照规则生成下一个状态 next.y = now.y + dir[i][1]; next.Step_Counter = now.Step_Counter + 1; // 计数器加1 if (CheckState(next)) // 如果状态满足约束条件则入队 { q.push(next); vst[next.x][next.y] = 1; //访问标记 } } q.pop(); // 队首元素出队 } return; } int main() { ...... return 0; }
模板题1
部分内容转自这里
最后
以上就是超级金针菇最近收集整理的关于BFS、DFS算法原理及代码模板(附模板题)的全部内容,更多相关BFS、DFS算法原理及代码模板(附模板题)内容请搜索靠谱客的其他文章。
发表评论 取消回复