vlambda博客
学习文章列表

搜索-深度优先搜索(DFS)

深度优先搜索(DFS)

DFS也是图中常见的搜索方法之一,本质是递归,同样需要强调的是DFS同样不止用于对图的搜索。

DFS思想啊

假设我们从点u开始搜索,需要找到点a_1,已知与点u有关系的点为v_1,v_2,与点v_1有关系的点为w_1,w_2,与点v_2有关系的点为a_1,a_2,我们如何通过这些关系找点a_1?你是否这样想过,通过点u找到v_1,通过v_1找到w_1,w_1没有其他关系,返回到v_1,通过v_1再找到w_2,w_2也没有其他关系,返回到v_1,v_1遍历完了所有关系,返回到u,通过u找到v_2,通过v_2找到a_1,找到了a_1返回一个找到的信息,结束递归。如果你这样想过,那恭喜你理解理解了DFS。

深度优先遍历图的方法是,从图中某顶点v出发:

  1. 访问顶点v;

  1. 依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;

  1. 若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。 

DFS与记忆化搜索

对于上面的由u找a_1的问题,上面的结构更确切的应该是树,如果再添加一组对应关系即w_1与a_1有关系,那我们找到w_1之后就通过w_1找到a_1了,这何时才能结束呀?仔细观察我们发现a_1已经在递归的过程中了,我们并不需要在对它进行一次递归。所以我们可以记录一下a_1已经被访问过了,别再来找它了。这样就避免了一直递归的情况。当然还有很多种不同的记忆方式,这种记忆化+DFS叫记忆化搜索,其实就是DFS。

在使用DFS与BFS的过程中我们为了减少重复访问而对某些数据进行储存,以便更快的进行搜索,这是DFS与BFS搜索的基本操作,所以见到记忆化搜索别大惊小怪了。就比如说最短路算法中(假设所有数据大于0),Dijkstra的堆优化就是对于SPFA增加了一些数据的储存,让Dijkstra的堆优化对稠密图的处理较好。

DFS与BFS还有一种名叫剪枝操作,就是让在搜索前后搜索中判定用不到的数据不参与搜索,也是为了加快搜索速度。

模板

void DFS(参数){ if(到底了||找到结果){ 一些操作; return; } 1.对现有数据进行处理 2.DFS(参数);}//1、2根据实际情况来分先后(就是递归模板)

例题 洛谷P1434

题目描述

Michael 喜欢滑雪。这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子:

1   2   3   4   5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度会减小。在上面的例子中,一条可行的滑坡为 24-17-16-1(从 24 开始,在 1 结束)。当然 25-24-23- ... -3-2-1 更长。事实上,这是最长的一条。

输入格式

输入的第一行为表示区域的二维数组的行数 R和列数 C下面是 R行,每行有 C个数,代表高度(两个数字之间用 1个空格间隔)。

输出格式

输出区域中最长滑坡的长度。

输入输出样例

输入 #1

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

输出 #1

25

说明/提示

对于100% 的数据,1≤R,C≤100。

例题分析

很简单,我们对每一个数进行DFS进行DFS查找,然后记录每一个点的的最大值,之后遍历一下记录点的数组找到最大值就是答案。是否有优化的空间呢?对于样例中的数字18,由题意知它可以像17与3划去,假设我们已经知道17与3对应的最大值,那么此时18访问到17,3就不需要再走一遍17,3的dfs过程。直接得出结果,对于递归语言的表达过于肤浅,作者放上一份弱弱的ac代码,供大家参考。

#include<iostream>#include<cstdio>using namespace std;int arr[110][110];//记录滑雪的区域 int brr[110][110];//记录对应点的最大能滑多长 int r[]={1,-1,0,0};//控制方向 int t[]={0,0,1,-1};//控制方向 int n,m;//滑雪场的大小 int dfs(int a,int b)//从那一个点开始dfs { if(brr[a][b]!=0)return brr[a][b];//brr有值,说明不需要再dfs  brr[a][b]=1;//对于每一个点,最小可以滑动的值为1,看题意...  for(int i=0;i<4;i++) { int wa=a+r[i];//控制方向  int wb=b+t[i];//控制方向  if(wa>0&&wa<=n&&wb>0&&wb<=m&&arr[a][b]>arr[wa][wb])//满足可以滑的条件  { brr[a][b]=max(brr[a][b],dfs(wa,wb)+1);//储存最大能滑的距离  } } return brr[a][b];//返回值 }//以下操作不为主要代码,不做解释 int main(){ scanf("%d%d",&n,&m); for(int a=1;a<=n;a++) { for(int b=1;b<=m;b++) { scanf("%d",&arr[a][b]); } } for(int a=1;a<=n;a++) { for(int b=1;b<=m;b++) { dfs(a,b); } } int ma=0; for(int a=1;a<=n;a++) { for(int b=1;b<=m;b++) { ma=max(ma,brr[a][b]); } } printf("%d\n",ma); }


关键字

DFS深度优先搜索记忆化搜索