
- 提出者
- 霍普克洛夫特与罗伯特·塔扬
- 应用学科
- 计算机
- 中文名
- 深度优先搜索
- 外文名
- Depth-First-Search
-
DFS
2017-03-26 11:00:43DFS实质就是一种枚举,不过借助递归实现; DFS的基本模式: void dfs(int step) { 判断边界; for(int i=1;i { dfs(step+1);/‘/继续下一步 } 返回; } 例题: 问题描述: 现有等式:【】【】【】+...DFS实质就是一种枚举,不过借助递归实现;
DFS的基本模式:
void dfs(int step)
{
判断边界;
for(int i=1;i<=n;++i)//尝试每一种可能;
{
dfs(step+1);/‘/继续下一步
}
返回;
}
例题:
问题描述:
现有等式:【】【】【】+【】【】【】=【】【】【】,要求在每一个【】中填入0~9中某一个数字,最后使得等式成立且每个数字使用一次,输出等式,并输出总个数;例如782+154=936,154+782=936只计数一次,但输出时都输出;
基本思路:
对每一个【】进行深搜;
代码如下:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int a[10],book[10];
int total;
void dfs(int step)
{
if(step==10)
{
if(a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6]==a[7]*100+a[8]*10+a[9])
{
for(int i=1;i<=9;i++)
{
printf("%d",a[i]);
if(i==3) printf("+");
else if(i==6) printf("=");
}
printf("\n");
total++;
}
}
for(int i=1;i<=9;i++)//可以体现枚举;
{
if(book[i]==0)
{
a[step]=i;
book[i]=1;
dfs(step+1);//对下一个【】进行深搜;
book[i]=0;//恢复;
}
}
return;
}
int main()
{
dfs(1);
printf("%d\n",total/2);
return 0;
} -
DFS(深度优先搜索算法)
2018-10-07 16:32:43深度优先搜索算法(Depth First Search,简称DFS):一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索将回溯到...基本概念
深度优先搜索算法(Depth First Search,简称DFS):一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。
算法思想
回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
基本模板
int check(参数) { if(满足条件) return 1; return 0; } void dfs(int step) { 判断边界 { 相应操作 } 尝试每一种可能 { 满足check条件 标记 继续下一步dfs(step+1) 恢复初始状态(回溯的时候要用到) } }
问题示例
1、全排列问题
//全排列问题 #include<stdio.h> #include<string.h> int n; char a[15]; char re[15]; int vis[15]; //假设有n个字符要排列,把他们依次放到n个箱子中 //先要检查箱子是否为空,手中还有什么字符,把他们放进并标记。 //放完一次要恢复初始状态,当到n+1个箱子时,一次排列已经结束 void dfs(int step) { int i; if(step==n+1)//判断边界 { for(i=1;i<=n;i++) printf("%c",re[i]); printf("\n"); return ; } for(i=1;i<=n;i++)//遍历每一种情况 { if(vis[i]==0)//check满足 { re[step]=a[i]; vis[i]=1;//标记 dfs(step+1);//继续搜索 vis[i]=0;//恢复初始状态 } } return ; } int main(void) { int T; scanf("%d",&T); getchar(); while(T--) { memset(a,0,sizeof(a)); memset(vis,0,sizeof(vis));//对存数据的数组分别初始化 scanf("%s",a+1); n=strlen(a+1); dfs(1);//从第一个箱子开始 } return 0; }
2、一个环由个圈组成,把自然数1,2,…,N分别放在每一个圆内,数字的在两个相邻圈之和应该是一个素数。 注意:第一圈数应始终为1。
input: N(0~20)
output:输出格式如下所示的样品。每一行表示在环中的一系列圆号码从1开始顺时针和按逆时针方向。编号的顺序必须满足上述要求。打印解决方案的字典顺序。
//Prime Ring Problem //与上面的全排列问题其实思路差不多,只是需要判断的条件比较多 //化大为小 #include<stdio.h> #include<string.h> #include<stdlib.h> int book[25]; int result[25]; int n; int num; //判断是否为素数 int prime(int n) { if(n<=1) return 0; int i; for(i=2;i*i<=n;i++) { if(n%i==0) break; } if(i*i>n) return 1; return 0; } //判断是否能将当前的数字放到当前的圈内 int check(int i,int step) { if((book[i]==0) && prime(i+result[step-1])==1) { if(step==n-1) { if(!prime(i+result[0])) return 0; } return 1; } return 0; } void dfs(int step) { if(step==n)//判断边界 { int a; printf("%d",result[0]); for(a=1;a<n;a++) { printf(" %d",result[a]); } printf("\n"); return ; } int i; for(i=2;i<=n;i++)//遍历每一种情况 { if(check(i,step))//check是否满足 { book[i]=1;//标记 result[step]=i;//记录结果 dfs(step+1);//继续往下搜索 book[i]=0;//恢复初始状态 } } } int main(void) { while(scanf("%d",&n)!=EOF) { num++; memset(result,0,sizeof(result)); memset(book,0,sizeof(book)); result[0]=1; printf("Case %d:\n",num);//格式比较容易出错 dfs(1); printf("\n"); } return 0; }
3、油田问题
问题:GeoSurvComp地质调查公司负责探测地下石油储藏。 GeoSurvComp现在在一块矩形区域探测石油,并把这个大区域分成了很多小块。他们通过专业设备,来分析每个小块中是否蕴藏石油。如果这些蕴藏石油的小方格相邻,那么他们被认为是同一油藏的一部分。在这块矩形区域,可能有很多油藏。你的任务是确定有多少不同的油藏。
input: 输入可能有多个矩形区域(即可能有多组测试)。每个矩形区域的起始行包含m和n,表示行和列的数量,
1<=n,m<=100,如果m =0表示输入的结束,接下来是n行,每行m个字符。每个字符对应一个小方格,并且要么是’*’,代表没有油,要么是’@’,表示有油。
output: 对于每一个矩形区域,输出油藏的数量。两个小方格是相邻的,当且仅当他们水平或者垂直或者对角线相邻(即8个方向)。
//A - Oil Deposits #include<stdio.h> #include<string.h> #include<stdlib.h> char a[105][105]; int n,m,result; int dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};//表示8个方向 int check(int x,int y)//检查是否有油田 { if(x>=0&&x<m&&y>=0&&y<n&&a[x][y]=='@') return 1; return 0; } int dfs(int x, int y) { int i,xx,yy; if(check(x,y)) { a[x][y]='.'; //统计之后就可以把该油田标记,且不用恢复(要不会重复), //也可以用一个数组来存每个点的访问情况,但是感觉没必要,浪费空间 for(i=0;i<8;i++) { xx=x+dir[i][0]; yy=y+dir[i][1]; dfs(xx,yy);//依次检查8个方向 } return 1; } return 0; } int main(void) { int i,j; while(scanf("%d %d",&m,&n)==2) { if(m==0&&n==0) break; result = 0; memset(a,0,sizeof(a)); for(i=0;i<m;i++) scanf("%s",a[i]); for(i=0;i<m;i++)//在每一个点都搜索一次 { for(j=0;j<n;j++) { if(dfs(i,j))//找到油田就可以将结果加1 result++; } } printf("%d\n",result); } return 0; }
4、棋盘问题
问题:在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。
input: 输入含有多组测试数据。 每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。
output:对于每一组数据,给出一行输出,输出摆放的方案数目C (数据保证C<2^31)。
#include<stdio.h> #include<string.h> #include<stdlib.h> int n, k, ans; char str[10][10]; int vis[100]; void dfs(int r, int k) { if(k==0)//判断边界,此时棋子已经放完 { ans++; return; } for(int i=r; i<n; i++)//每次都从放过棋子下一行开始搜索,保证不重复 { for(int j=0; j<n; j++) { //循环保证行不重复,check保证列不重复 if(str[i][j]=='.' || vis[j]==1) continue;//不满足条件直接跳过 vis[j] = 1;//标记 dfs(i+1, k-1);//继续下一次标记 vis[j] = 0;//恢复初始状态 } } } int main(void) { while(1) { scanf("%d %d", &n, &k); getchar(); if(n==-1 && k==-1) break; memset(str, '\0', sizeof(str)); memset(vis, 0, sizeof(vis)); ans = 0; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) str[i][j] = getchar(); getchar(); } dfs(0, k);//从第0行开始放,此时手中还剩k个棋子 printf("%d\n", ans); } return 0; }
参考文章
https://blog.csdn.net/ldx19980108/article/details/76324307#commentBox
-
DFS原理白话解析
2018-11-04 11:20:57看了许多的关于dfs的博客,自己也研究了好多遍,最终算是入门了,下面就简单的个人理解的原理以及结合一个简单的全排列实例进行讲解。 原理简介 dfs基于递归思想,递归思想就是把一个事拆分成若干见相同的小事共同...前言
看了许多的关于dfs的博客,自己也研究了好多遍,最终算是入门了,下面就简单的个人理解的原理以及结合一个简单的全排列实例进行讲解。
原理简介
DFS基于递归思想,递归思想就是把一个事拆分成若干见相同的小事共同组合完成,具体见下图的斐波那契的图文解决
这就是一个最典型的递归,入口f(5)出口就是每次递归的return;
说完递归就是dfs,其有两个重要的标志,也就是两个数组,一个用来标记该点是否被访问过,一个用来把该点放入数组,所以这两个标记是相辅相成的,一定同时出现;dfs就是随机选定一个起点将其标记为已经访问过的点,然后就是递归调用进行与其相邻的点的搜索,直到所有的点都被访问完。
话不多说上例子
全排列,也就是1-n,输出其所有的排列结果。
代码如下,接下来会详细解读代码:#include <stdio.h> #include <iostream> using namespace std; int a[101],b[101],n; void print() { int i; for(i=1;i<=n;i++) { cout<<a[i]<<' '; } cout<<endl; } inline void dfs(int i) { int j; if(i==n+1) { print(); return; } for(j=1;j<=n;j++) { if(b[j]==0) { a[i]=j; b[j]=1; dfs(i+1); b[j]=0; } } } int main() { ios::sync_with_stdio(false); cin>>n; dfs(1); return 0; }
注:以上代码来自csdn博客 Apro1066。
这个代码看上去不多,但是确实经典,有好多值得推敲的东西。
首先主函数中的dfs(1)
这是dfs函数进入,传入参数1就是从1开始,主要在dfs函数的理解,下面的图片展示了展示了这个过程。
下面是一个DFS的经典问题-走迷宫,大家可以结合代码做进一步的理解。
Code
#include<bits/stdc++.h> using namespace std; bool a[101][101]={0}; char b[101][101]; //存放迷宫 int flag=0; //如果能走出去就标记为1,反之为0 int xx[4]={0-1,0,1},yy[4]={-1,0,1,0}; int n,kx,ky; //n是迷宫的边长,kx是x进行加减之后的值,同理ky。 void dfs(int x,int y){ for(int i=0;i<=3;i++){ kx=x+xx[i]; ky=y+yy[i]; if((b[kx][ky] == '.'||b[kx][ky] == 'e')&&kx>=0&&ky>=0&&kx<n&&ky<n&&a[kx][ky]==0){ a[kx][ky]=1; if(b[kx][ky] == 'e'){ flag = 1; }else{ dfs(kx,ky); } } } } int main(){ int k=1,sum; cin>>sum; while(k<=sum){ memset(a,0,sizeof(a)); //将标记数组a全部记为 0,表示这个点未走过 cin>>n; for(int i = 0;i<n;i++){ for(int j=0;j<n;j++) cin>>b[i][j]; } for(int i = 0;i<n;i++){ for(int j=0;j<n;j++){ if(b[i][j]=='s') dfs(i,j); } } if(flag==1){ cout<<"YES"<<endl; }else{ cout<<"NO"<<endl; } k++; } return 0; }
有不懂的地方或者有错误的地方欢迎评论批评指正。
-
DFS理解(java)
2020-03-30 16:09:51DFS(深度优先搜索) /* DFS(深度优先搜索),“深度”是关键,以走迷宫为例,不撞南墙不回头,先找到最深的,然后回溯到上一个路口,以此类推。 有上述可知,DFS可由递归实现,所谓的南墙就是递归边界。 */ //...DFS(深度优先搜索)
/* DFS(深度优先搜索),“深度”是关键,以走迷宫为例,不撞南墙不回头,先找到最深的,然后回溯到上一个路口,以此类推。 有上述可知,DFS可由递归实现,所谓的南墙就是递归边界。 */ //package app; import java.util.Scanner; class DFSTest{ final static int maxn = 30; static int maxValue = 0; static int ans = 0; static int[] w = new int[maxn]; //用于存放每个点的质量 static int[] c = new int[maxn]; //用于存放对应点的价值或者说权重 static int n,V; //n是有几点个点,V是能接受点的质量的最大总和 public static void main(String[] args) { Scanner input = new Scanner(System.in); n = input.nextInt(); //输入有几个点 V = input.nextInt(); //输入能存放最大点的质量的总和 for(int i=0;i<n;i++){ //输入每个点的质量 w[i] = input.nextInt(); } for(int i=0;i<n;i++){ c[i] = input.nextInt();//输入每个点的权重 } input.close(); dfs(0, 0, 0); dfs1(0, 0, 0); System.out.println(maxValue); System.out.println(ans); } public static void dfs(int index, int sumW, int sumC){//index是每个点对应的序号,sumW是质量总和,sumC是权重总和或者说是价值总和 if(index == n){ if(sumW <= V && sumC > maxValue){ maxValue = sumC; } return; } dfs(index+1, sumW, sumC); dfs(index+1, sumW+w[index], sumC+c[index]); } public static void dfs1(int index, int sumW, int sumC){//剪枝后的DFS if(index == n){ return; } dfs1(index+1, sumW, sumC); if(sumW + w[index]<=V){ if(sumC + c[index] > ans){ ans = sumC + c[index]; } dfs1(index+1, sumW+w[index], sumC+c[index]); } } }
-
关于独立DFS和域DFS板书
2020-06-08 10:55:04独立DFS:解决了企业大量共享目录的虚拟目录树问题,把所有的共享都链接到DFS root上。 主域控制器、额外域控制器,都是用同样的域名 基于域的DFS: 1、可以有多级链接,实现共享资源的分类管理 产品类、 交换机 ... -
BFS 、DFS区别,详解
2017-08-18 21:14:36BFS 、DFS区别,详解写在最前的三点: 1、所谓图的遍历就是按照某种次序访问图的每一顶点一次仅且一次。 2、实现bfs和dfs都需要解决的一个问题就是如何存储图。一般有两种方法:邻接矩阵和邻接表。这里为简单起 ... -
DFS子集
2017-11-26 10:51:22DFS子集 -
DFS IDFS 离散傅里叶级数
2014-06-24 20:37:39DFS IDFS 离散傅里叶级数 -
DFS 树
2020-03-27 07:55:55翻译自 THe DFS tree and its applications: how I found out I really didn’t understand bridges 介绍 这是一篇对可以用图的 DFS 树来解的题的教程/扩展。 在很长一段时间,我并没有真正理解传统算法是如何找到桥... -
DFS入门
2018-09-09 10:41:00因为感觉自己学艺不精啊,BFS和DFS都是一种搜索算法,我感觉BFS没有那么难,因为他比较好理解,但是DFS因为牵扯到递归和回溯等,不太好理解,但是他的实用性是毋庸置疑的,所以即使这个算法再难,我们还是要试着去... -
DFS 复制
2018-09-02 11:53:02掌握 Windows Server 2016 分布式网络服务的应用场景,理解 DFS 命名空间,复制,BranchCache 的基本组件,工作原理,能够规划,部署和配置多站点和多分支机构场景中,DFS 命名空间服务,DFS 复制和 BranchCache ... -
DFS模板
2019-04-05 20:48:36在大多数情况下,我们在能使用 BFS 时也可以使用 DFS。但是有一个重要的区别:遍历顺序。 与 BFS 不同,更早访问的结点可能不是更靠近根结点的结点。因此,你在 DFS 中找到的第一条路径可能不是最短路径。 模板-递归... -
dfs序
2017-02-22 08:05:20题: bzoj3779——lct+线段树+dfs序 bzoj4034——树剖….. bzoj3991——set+dfs序 bzoj3881——fail树+dfs序/树剖 bzoj3786——lct特殊姿势 bzoj2819——博弈+dfs序 -
non dfs used 和dfs remaining区别
2019-09-19 09:41:27DFS Used hadoop文件系统所使用的空间Non DFS Used 非hadoop文件系统所使用的空间,比如说本身的linux系统使用的,或者存放的其它文件 转载于:http... -
DFS复制
2017-06-03 12:37:36DFS复制 DFS复制,前身是Windows2000 Server操作系统中引入的文件复制服务(FRS),是一个基于状态的新型多主机复制引擎,支持复制计划和带宽限制。DFS复制使用一种称为远程差分压 缩(RDC)的新的压缩算法。RDC是一... -
DFS算法
2017-05-25 10:54:43今天做的DFS算法题目,牢牢把握dfs每次达到允许条件就递归,不然就回溯然后跳出本次函数 这个原理 -
dfs.namenode.name.dir 和dfs.datanode.data.dir dfs.name.dir 与 dfs.data.dir的意思
2020-05-12 15:26:27dfs.namenode.name.dir 和dfs.datanode.data.dir分别是什么目录? dfs.namenode.name.dir 和dfs.datanode.data.dir分别是什么目录?有何作用?我们可以在本地文件系统中找到HDFS文件系统中文件或目录的位置吗? 我们... -
C++ 实现DFS和DFS通用代码模板
2020-07-17 15:56:13第八章 DFS和BFS应用 深度优先搜索(DFS) 主要思想:递归 核心代码: void dfs(int x, int y){ int next[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int tx,ty; for(int i = 0; i < 4; i++){ tx = x + ... -
hdfs dfs -ls 与 hdfs dfs -ls / 区别
2019-08-25 17:02:25hdfs dfs -ls hdfs dfs -ls / hdfs dfs -ls hdfs://ip:9000/ 结果是否相同 hdfs dfs -ls 默认目录是在hdfs文件系统的/user/用户名 hdfs dfs -ls == hdfs dfs -ls /user/hadoop hdfs dfs -ls [hadoop@hadoop000 bin... -
DFS入门级教程,看完便完全掌握DFS
2020-08-16 18:09:58DFS 最近一直都在写蓝桥杯的题目,其中有许多题目涉及到了搜索(DFS,BFS)等,由于递归过于抽象,所以没能很好的掌握。于是便写下了这篇入门教程来加深对DFS的认识,并且充分理解递归。 所谓DFS就是指:优先考虑... -
DFS 解题套路
2020-03-17 17:47:42DFS 解题套路 如果碰到一个 DFS 题目,基本的代码套路如下: 1、我们基本都是使用递归来解决 DFS 问题,因此要确定递归的结束条件,也就是 DFS 结束条件。 2、写 DFS 函数套路框架。如下所示 void dfs() { } ... -
dfs和bfs差别_BFS和DFS之间的区别
2020-09-14 01:52:44Here you will learn aboutdifference between BFS and DFS algorithm or BFS vs. DFS. 在这里,您将了解BFS和DFS算法或BFS与DFS之间的区别。 Breadth First Search (BFS) and Depth First Search (DFS) are two ... -
hadoop fs、hadoop dfs和hdfs dfs的区别
2020-02-01 14:26:271、fs、dfs区别? (1) fs是文件系统, dfs是分布式文件系统。 (2) fs > dfs。 (3) 分布式环境情况下,fs与dfs无区别。 (4) 本地环境中,fs就是本地文件,dfs就不能用了。 (5) fs涉及到一个通用的文件系统,可以... -
BFS和DFS算法原理(通俗易懂版)
2016-11-16 17:25:32DFS 算法 思想:一直往深处走,直到找到解或者走不下去为止 BFS算法 DFS:使用栈保存未被检测的结点,结点按照深度优先的次序被访问并依次被压入栈中,并以相反的次序出栈进行新的检测。 BFS:使用队列... -
DFS优化
2017-11-08 10:34:00DFS是常用的暴力方法,但由于其O(n!)的效率,有时难以通过较多数据点,所以需对其进行剪枝。范围剪枝:(一种可行性剪枝,拉出来单独讲) 有时DFS的范围较大会导致TLE,这时需根据题意缩小搜索的范围。例如:... -
dfs全排列
2016-12-06 21:43:01import java.util.Scanner; import java.math.BigDecimal;...public class dfs { public static int []arr=new int[1000]; public static int []flag=new int[1000];//标志哪些数字已经被用 public static void dfs -
常用hadoop dfs命令
2018-03-29 21:14:45hadoop dfs -mkdir /home 上传文件或目录到hdfs hadoop dfs -put hello / hadoop dfs -put hellodir/ / 查看目录 hadoop dfs -ls / 创建一个空文件 hadoop dfs -touchz /361way 删除一个文件 hadoop... -
简单易懂DFS(一) dfs + 回溯
2019-03-01 00:35:37DFS 深度优先搜索,简称∗∗dfs∗∗**dfs**∗∗dfs∗∗ 深度优先搜索按照深度优先的方式进行搜索,通俗来说就是"一条路走到黑"。注意,这里的"搜索"不是指的我们平时在文件中或者在网络上查找...
-
#数据结构基础知识----数组
-
红米6维修原理图PCB位置图(PDF格式)
-
功能测试方法.xmind
-
云计算基础-Linux系统管理员
-
QTdesigner布局
-
转行做IT-第5章 流程控制语句
-
MySQL锁总结【摘录】
-
Redis数据库入门与使用
-
转行做IT-第6章 IDEA、方法
-
Oracle数字函数
-
算法导论(基础知识)——编程大牛的必经之路
-
Java Web开发之Java语言基础
-
hadoop自动化运维工具Ambari应用实践
-
SubstancePainter插件开发-基础入门
-
chromium 编译 google_play_services打包
-
保持一颗谦逊的心
-
小米5X维修原理图PCB位置图(PDF格式)
-
深搜与广搜
-
【数据分析-随到随学】数据分析建模和预测
-
电商设计专业思维