DFS与BFS

2024-05-24 17:29| 来源: 网络整理| 查看: 265

新的方法和概念，常常比解决问题本身更重要。————华罗庚

引子

深度优先搜索（Deep First Search）广度优先搜索（Breath First Search）当菜鸟们（比如我）初步接触算法的时候，会接触这两种简单的盲目搜索算法，相较与其他众多的算法，这两种算法相对较好理解，运用范围也很广，在众多的学科竞赛里都可以见到它们的影子，话不多说，我们开始。

深度优先搜索（Deep First Search）深度优先搜索算法（Depth First Search）：一种用于遍历或搜索树或图的算法。沿着树的深度遍历图的节点，尽可能深的搜索图的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

做一个形象的比喻，dfs好比走迷宫，得一直走到头，看看路的尽头是不是出口，如果是，就直接走出去，如果不是，那就返回上一个“标记点”寻找不一样的可行方法。 dfs的实现关键在于回溯，这个可以用两种方法实现（递归、堆栈），以下给出伪代码

递归实现：

递归实现是dfs最广泛的使用方法。

void dfs(int x,int y) { if(达到出口||无法继续) { 相应操作; return； } if（对应x方向的下一步可以继续） { 添加标记;//给该位置记上标记，如果后续递归调用碰到了这个点，则该方向不能继续下一步 dfs(x+1,y);//调用递归取消标记;//上一步对应的递归操作全部结束，则要取消标记对后续操作的影响 } else if（对应y方向的下一步可以继续）{ 添加标记; dfs(x,y+1); 取消标记; } } 栈实现：

栈实现的基本思路是将一个节点所有未被访问的“邻居”（即“一层邻居节点”）压入栈中“待用”，然后围绕顶部节点进行判定，每个节点被访问后被踹出，为了代码的简洁易懂，使用了c++的stl。

void dfs_stack(int start, int n) { stack s;//创建栈 for (int i=0;i 标记访问; s.push(i);//入栈 } } while (!s.empty()) {//如果栈非空访问s.top()（栈顶）; 相应操作; s.pop();//出栈 for (int i = 1; i 标记访问 s.push(i);//入栈 } } } } 例题理解洛谷 P2392 kkksc03考前临时抱佛脚：题目背景 kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。题目描述这次期末考试，kkksc03 需要考 4 科。因此要开始刷习题集，每科都有一个习题集，分别有 s1,s2,s3,s4 道题目，完成每道题目需要一些时间，可能不等。 kkksc03 有一个能力，他的左右两个大脑可以同时计算 2道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。输入格式本题包含 5 行数据：第 1 行，为四个正整数 s1,s2,s3,s4。第 2 行，为 A1,A2,…,As1 共 s1 个数，表示第一科习题集每道题目所消耗的时间。第 3 行，为 B1,B2,…,Bs2 共 s2 个数。第 4 行，为 C1,C2,…,Cs3 共 s3 个数。第 5 行，为 D1,D2,…,Ds4 共 s4 个数，意思均同上。输出格式输出一行,为复习完毕最短时间。输入输出样例输入 1 2 1 3 5 4 3 6 2 4 3 输出 20 AC代码 #include #define LL long long #define INF 0x3f3f3f3f using namespace std; int Left, Right, minn, ans=0; int s[5]; int a[21][5]; void dfs(int x, int y) { if (x > s[y]) {//任务全部分配完毕，做最后处理 minn = min(minn, max(Left, Right)); return; } Left += a[x][y];//任务丢给左脑(标记) search(x + 1, y); Left -= a[x][y];//把左脑的任务抽出给右脑（取消标记） Right += a[x][y];//任务丢给右脑(标记) search(x + 1, y); Right -= a[x][y];//把右脑的任务抽出给左脑（取消标记） } int main() { cin >> s[1] >> s[2] >> s[3] >> s[4]; for (int i = 1; i queue qu;//创建队列 qu.push(起始状态入队)； while(!qu.empty()){//当队列非空 if(当前状态x方向可走) qu.push(当前状态+x);//该状态入队 if(当前状态向y方向可走) qu.push(当前状态+y);//该状态入队 ………………… 处理(队顶)qu.top(); 相应操作； qu.pop();//队首弹出队 }//一次循环结束，执行下一次循环 } 例题理解 OpenJ_Bailian - 2790 迷宫题目背景

一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。

Input

第1行是测试数据的组数k，后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 1,0},{-1,0},{0,1},{0,-1}};//方向 struct node { int x,y;//横纵坐标 }; node now,net; void bfs() { int f=0; queueq; now.x=sx,now.y=sy; mp[now.x][now.y]='#';//这里走过变'.'为'#'即可 q.push(now); while(!q.empty()) { now=q.front(); q.pop(); if(now.x==ex&&now.y==ey)//到达终点 { f=1; cout q.push(net); mp[net.x][net.y]='#';//这里走过变'.'为'#'即可 } } } if(f==0) { cout cin>>n; for(int i=0; imp[i][j]; cin>>sx>>sy>>ex>>ey; // cout

【本文地址】

DFS与BFS

DFS与BFS

今日新闻

推荐新闻