DFS的理解和应用_Mic_H的博客 - CSDN

目录DFS(Depth First Search)数塔问题Prime Ring Problem - HDOJ 1016 / UVa 524 /（紫书P194例题7-4）Zipper HDOJ - 1501（DFS+剪枝）Lake Counting ... DFS的理解和应用 置顶 Mic_H 2018-08-0810:31:58 8584 收藏 116 分类专栏： 算法--理解与应用 DFS 文章标签： DFS理解和应用 版权声明：本文为博主原创文章，遵循CC4.0BY-SA版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/qq_41759198/article/details/81501764 版权 算法--理解与应用 同时被2个专栏收录 7篇文章 0订阅 订阅专栏 DFS 2篇文章 0订阅 订阅专栏 目录 DFS(DepthFirstSearch) 数塔问题 PrimeRingProblem-HDOJ1016/UVa524/（紫书P194例题7-4） ZipperHDOJ-1501（DFS+剪枝） LakeCountingPOJ-2386 棋盘问题POJ-1321 水果消除HNUSTOJ  团队程序设计天梯赛--L3-015 球队“食物链” 数独挑战 DFS(DepthFirstSearch) 算法竞赛中的一个重要技巧，在许多题目里，用DFS有着神奇的作用。

利用栈这种数据结构来实现（找到的第一个解不一定是最优解，只是先序遍历最早的可行解） 案例解释：走迷宫 看到哪个方向可以走就走哪个，而且你没有办法分身，所以只能慢慢试探，不撞南墙不回头。

数塔问题 题目描述: 输入一个三角形塔，从三角塔顶出发向下走，每个点都有不同的权值，走到那个点就获得对应的权值，求走到塔底的时候能够获得的权值的最大值。

SampleInput 4 5 8 4 3 6 9 7 2 9 5 SampleOutput 28 评论区反映这个塔不知道是怎么走的，这个塔其实就是这样的 每一个点只能走下属的两个分支的其中一个，所以，DFS的路径是5→8→6→9，5+8+6+9=28. 先来一个最普通的代码。

///数塔1.0 #include #include #include #include #include #defineMAX100010 usingnamespacestd; intn; inta[200][200]; intDFS(inti,intj) { if(i==n) returna[i][j]; intx=DFS(i+1,j); inty=DFS(i+1,j+1); returnmax(x,y)+a[i][j]; } intmain() { while(cin>>n) { for(inti=1;i<=n;i++) for(intj=1;j<=i;j++) cin>>a[i][j]; cout< #include #include #include #include #include #defineMAX100010 usingnamespacestd; intn; inta[200][200]; intvis[200][200]; intDFS(inti,intj) { if(vis[i][j]!=-1) returnvis[i][j]; if(i==n)///endofthisroad vis[i][j]=a[i][j];///savetheresult else { intx=DFS(i+1,j); inty=DFS(i+1,j+1); vis[i][j]=max(x,y)+a[i][j]; } returnvis[i][j]; } intmain() { while(cin>>n) { memset(a,0,sizeof(a)); memset(vis,0xff,sizeof(vis)); for(inti=1;i<=n;i++) for(intj=1;j<=i;j++) cin>>a[i][j]; cout< #include #include usingnamespacestd; intvis[25]={0}; intn,num[25]={0}; intis_prime(intk)///判断素数，也可以打表，那样更快 { inti; for(i=2;i<=sqrt(k);i++) if(k%i==0) return0; return1; } voidDFS(intk) { inti; if(k>n&&is_prime(num[n]+num[1]))///测试最后一个数和第一个数之和是否为素数 { for(i=1;i>n) { if(n<1||n>19) break; printf("Case%d:\n",cnt++); num[1]=1; DFS(2); printf("\n"); } return0; } ZipperHDOJ-1501（DFS+剪枝） 题目描述：给出两个字符串，问能否在不改变字符串本身顺序的情况下，拆开重组成指定字符串，输出yes/no。

SampleInput 3 cattreetcraete cattreecatrtee cattreecttaree SampleOutput Dataset1:yes Dataset2:yes Dataset3:no   ( ˙˘˙ )没想到吧，这题居然也能用DFS。

分析：从三个串的首元素开始，遇到一串/二串与目标串匹配的字母，继续向下DFS，如果这些可以到达目标串的尾元素，那么意味着前面的都匹配成功，所以这个结果是yes，否则no。

//ZipperHDOJ1501 #include #include usingnamespacestd; chara[209],b[209],c[409]; intvis[209][209]={0}; intOK=0; voidDFS(inti,intj,intk) { if(vis[i][j]==1)///已经访问过，剪掉 return; if(c[k]=='\0')///到指定字符串的结尾，说明之前的都匹配成功 { OK=1; return; } if(a[i]!='\0'&&c[k]==a[i])//匹配成功 DFS(i+1,j,k+1); if(b[j]!='\0'&&c[k]==b[j])//匹配成功 DFS(i,j+1,k+1); vis[i][j]=1;///cut } intmain() { intn,i,j,cnt=0; cin>>n; while(n--) { OK=0; for(i=0;i<209;i++)///cut for(j=0;j<209;j++) vis[i][j]=0; scanf("%s%s%s",a,b,c); DFS(0,0,0); printf("Dataset%d:%s\n",++cnt,OK?"yes":"no"); } return0; } LakeCountingPOJ-2386 题目描述：给出一张n*m的地图，求图中水洼的个数。

水洼的大小不定，如果W的四周也有W，这些W组成一个大的水洼。

SampleInput 1012 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W. SampleOutput 3 分析：找到‘W’的地，然后对其四周进行判断（DFS），并且把它附近全部变成‘.’，计算这样做的次数，即为池塘的个数。

//LakeCountingPOJ2386 #include #include #include usingnamespacestd; charfarm[109][109]; intn,m; voiddfs(intx,inty) { farm[x][y]='.'; inti,j; inttx,ty; for(i=-1;i<=1;i++) { for(j=-1;j<=1;j++) { tx=x+i; ty=y+j; if((tx>=0&&tx=0&&ty>n>>m) { intsum=0; getchar(); for(i=0;i>farm[i][j]; getchar(); } for(i=0;i #include #include usingnamespacestd; ///noticethatthe'#'canbeplaced intn,m; intans=0; charmap[10][10]; intvis[10]; voidDFS(intx,intstep) { if(step==m)///foundawaythatwork { ans++; return; } if(x==n) return; DFS(x+1,step); for(intj=0;j>n>>m) { if(n==-1&&m==-1) break; ans=0; memset(vis,0,sizeof(vis)); for(inti=0;i #include usingnamespacestd; ///noticethatthe'#'canbeplacedwhile'.'not intmap[1000][1000]; intdir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; intn; intnum; voidDFS(intx,inty,intk) { map[x][y]=0; inti; inttx,ty; for(i=0;i<4;i++) { tx=x+dir[i][0]; ty=y+dir[i][1]; if(tx>=0&&tx=0&&ty>n) { intsum=0; for(inti=0;i1) sum++; } printf("%d\n",sum); } return0; } 团队程序设计天梯赛--L3-015 球队“食物链” 题目链接 某国的足球联赛中有N支参赛球队，编号从1至N。

联赛采用主客场双循环赛制，参赛球队两两之间在双方主场各赛一场。

联赛战罢，结果已经尘埃落定。

此时，联赛主席突发奇想，希望从中找出一条包含所有球队的“食物链”，来说明联赛的精彩程度。

“食物链”为一个1至N的排列{ T​1​​ T​2​​ ⋯ T​N​​ }，满足：球队T​1​​战胜过球队T​2​​，球队T​2​​战胜过球队T​3​​，⋯，球队T​(N−1)​​战胜过球队T​N​​，球队T​N​​战胜过球队T​1​​。

现在主席请你从联赛结果中找出“食物链”。

若存在多条“食物链”，请找出字典序最小的。

注：排列{ a​1​​ a​2​​ ⋯ a​N​​}在字典序上小于排列{ b​1​​ b​2​​ ⋯ b​N​​ }，当且仅当存在整数K（1≤K≤N），满足：a​K​​ usingnamespacestd; constintmaxn=30; charar[maxn][maxn]; intN; intw[maxn][maxn]; boolvis[maxn]; intans[maxn]; booldfs(inti,intnum) { if(num==N&&w[i][0])///都走到这里了，答案肯定已经确定了 { for(intk=0;k=N)///怎么都不能形成环 returnfalse; for(intj=1;j>N; for(inti=0;i>ar[i]; for(inti=0;i>... 深度优先搜索(DFS)总结(算法+剪枝+优化总结) HeartFireY的博客 11-10 5649 深度优先搜索(DFS)总结(算法+剪枝+优化总结) 本文中会引用部分实例、文献资料来自不同的作者之手，由于资料整理比较困难，转载地址不在文中列举。

如有侵权请联系我更换或删除！对于提供题解思路的各位大佬和作者：非常感谢！ 一、前导 定义上的深度优先搜索的思路与树的先序遍历非常相似，是针对图的搜索而提出的一种算法，下面是算法导论上的解释： 在深度优先搜索中，对于最新发现的顶点，如果它还有以此为顶点而未探测到的边，就沿此边继续探测下去，当顶点v的所有边都已被探寻过后，搜索将回溯到发现顶点v有起始点的那些边 BFS和DFS算法原理（通俗易懂版） 热门推荐 尚小馨的博客 11-16 17万+ DFS算法 思想：一直往深处走，直到找到解或者走不下去为止 BFS算法 DFS：使用栈保存未被检测的结点，结点按照深度优先的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。

BFS：使用队列保存未被检测的结点。

结点按照宽度优先的次序被访问和进出队列。

框架： BFS: #include #include #include #include 图的基本算法(BFS和DFS) weixin_34223655的博客 04-07 1017 图是一种灵活的数据结构，一般作为一种模型用来定义对象之间的关系或联系。

对象由顶点（V）表示，而对象之间的关系或者关联则通过图的边（E）来表示。

图可以分为有向图和无向图，一般用G=(V,E)来表示图。

经常用邻接矩阵或者邻接表来描述一副图。

在图的基本算法中，最初需要接触的就是图的遍历算法，根据访问节点的顺序，可分为广度优先搜索（BFS）和深度优先搜索（DFS）。

广度优先搜索（BFS）广度... BFS和DFS的应用 summer_cai的博客 06-02 301 130.被围绕的区域 https://leetcode-cn.com/problems/surrounded-regions/ publicvoidsolve(char[][]board){ if(board.length<3||board[0].length<3){ return; } ... DFS算法应用 weixin_43165059的博客 02-26 723 一、DFS模板： intcheck(参数) { if(满足条件) return1; return0; } voiddfs(intstep) { 判断边界 { 相应操作 } 尝试每一种可能 { 满足check条件 ... DFS简单应用 jelly的博客 02-24 162 DFS的入门应用 有n件物品，每件物品的重量为w[i],价值为c[i].现在需要选出若干件物品放入一个容量为v的背包中，使得在选入背包的物品重量和不超过容量v的前提下，让背包中物品的价值之和最大，求最大的价值。

（1&amp;lt;=n&amp;lt;=20） 分析：将每个点的选与不选作为两种转态，利用DFS，在将选与不选作为状态后，遍历全部的n个点，找出其中的最大值，其中边界为不超过容量v和遍历完n个点，复杂度为... 关于dfs的一点小小理解 yangzijiangac的博客 12-30 704 先来一个板子： intmov[4][2]={0,1,0-1,1,0,-1,0};//表示移动方向 voiddfs(intx,inty) { if(x==4&&y==4)//结束条件 { flag=1; return; } for(inti=0;i<4;++i) { intxx=x+mov[i][0]; intyy=y+mov... DFS（深度优先搜索） rootkiss的博客 09-13 391 求有向图中的最短路径（JAVA+DFS算法实现） 问题描述 给定一个有向图，如下图所示，求从1号顶点到5号顶点的最短路径。

输入数据格式为第一行输入顶点数和边数，从第二行开始每一行输入3个整数，分别代表连接顶点的边和权重。

例如：122，表示从1号顶点到2号顶点连接的边，权重为2。

Input： 58 122 1510 233 257 314 344 455 5... DFS入门级（模板） 浮生未歇 08-16 2万+ DFS 最近一直都在写蓝桥杯的题目，其中有许多题目涉及到了搜索（DFS，BFS）等，由于递归过于抽象，所以没能很好的掌握。

于是便写下了这篇入门教程来加深对DFS的认识，并且充分理解递归。

所谓DFS就是指：优先考虑深度，换句话说就是一条路走到黑，直到无路可走的情况下，才会选择回头，然后重新选择一条路。

1.全排列（入门引导） 引导题：输入一个数n，输出n的全排列 可以先把这个问题形象化 如： 假如有编号为1,2,3的3张扑克牌和编号为1,2,3的3个盒子。

将这3张扑克牌分别放入3个盒子一共有几种不同的放 DFS--基本入门模板和例题（绝对入门）(最全) RomanticChopininCSharpMinor 08-13 3万+ 以下是全网收集整理的和自己写的部分，绝对保证dfs轻松入门。

核心代码： 关于dfs参数问题，什么在变化，就把什么设置成参数。

voiddfs()//参数用来表示状态 { if(到达终点状态) { ...//根据题意添加 return; } if(越界或者是不合法状态) ... DFS概念介绍 fhaoi的博客 06-27 634 深度优先遍历（DepthFirstSearch,简称DFS）与广度优先遍历（BreathFirstSearch）是图论中两种非常重要的算法，生产上广泛用于拓扑排序，寻路（走迷宫），搜索引擎，爬虫等，也频繁出现在leetcode，高频面试题中。

本文将会从以下几个方面来讲述深度优先遍历，广度优先遍历，相信大家看了肯定会有收获。

深度优先遍历，广度优先遍历简介 习题演练 DFS，BFS在搜索引擎中的应用 深度优先遍历简介 1、深度优先遍历 深度优先遍历主要思路是从图中一个未访问的顶点V dfs算法的使用 Tongqi 02-26 1662 算法思想，dfs算法是一个递归的过程，有回退的过程，对于一个无向连通图，访问图中某个顶点v0后，然后访问它的某一个邻接顶点v1，然后再从v1出发，访问v1的违访问过的邻接顶点，如此下去，直至到达所有的领接顶点都被访问过。

然后回退一步，回到前一次被访问的顶点，看是否还有没有访问的顶点，如果有，则从这个顶点出发，进行向上述的过程一样进行访问，如果没有，则再回退一步，进行类似的访问，直至所有的顶点都被访... DFS(深度优先搜索算法) 无限迭代中...... 12-04 11万+ 基本概念 深度优先搜索算法（DepthFirstSearch，简称DFS）：一种用于遍历或搜索树或图的算法。

沿着树的深度遍历树的节点，尽可能深的搜索树的分支。

当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。

整个进程反复进行直到所有节点都被访问为止。

属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

算法思想 回溯法（探索与回溯法... DFS算法详解 sinat_35121480的博客 11-04 5万+ 作为搜索算法的一种，DFS对于寻找一个解的NP（包括NPC）问题作用很大。

但是，搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法，它的效率非常低，在数据规模变大时，这种算法就显得力不从心了。

当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。

这一过程一直进行到已发现从源节点可达的所有节点为止。

如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到 DFS（深度优先搜索，附例题） 最新发布 阳光的博客 11-18 145 ACWING842排列数字 题目描述 给定一个整数n，将数字1~n排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式 共一行，包含一个整数n。

输出格式 按字典序输出所有排列方案，每个方案占一行。

数据范围 1≤n≤7 样例 输入样例： 3 输出样例： 123 132 213 231 312 321 #include usingnamespacestd; intpath[100],st[100] ©️2021CSDN 皮肤主题:精致技术 设计师:CSDN官方博客 返回首页 Mic_H CSDN认证博客专家 CSDN认证企业博客 码龄4年 暂无认证 29 原创 11万+ 周排名 96万+ 总排名 5万+ 访问 等级 830 积分 43 粉丝 89 获赞 39 评论 382 收藏 私信 关注 热门文章 BFS的理解和应用 20310 小程序调用接口实例 12600 DFS的理解和应用 8569 C语言实现读者写者问题（读者优先） 7656 哲学家进餐问题--Linux下实现进程间的通信 1915 分类专栏 算法--理解与应用 7篇 题解 10篇 错排 2篇 DFS 2篇 BFS 1篇 莫队算法 1篇 Leetcode 8篇 小程序 最新评论 哲学家进餐问题--Linux下实现进程间的通信 m0_63127215: 哦哦，抱歉理解错了 哲学家进餐问题--Linux下实现进程间的通信 Mic_H: thinking就会释放，检查了一下输出，没有发现你说的情况 哲学家进餐问题--Linux下实现进程间的通信 m0_63127215: 五支筷子最多两个人在eating,为什么这个运行可以3个在eating呀 小程序调用接口实例 Mic_H: resdata只是一个变量名，不代表什么，具体看一下wxml和js之间是怎么用resdata的就能明白了 小程序调用接口实例 今天码了没: 想请问一下作者在js里的data包都有啥？要加上resdata吗？ 您愿意向朋友推荐“博客详情页”吗？ 强烈不推荐 不推荐 一般般 推荐 强烈推荐 提交 最新文章 数据挖掘——几个算法的python实现 STL（所见过的技巧和用法总结） 哲学家进餐问题--Linux下实现进程间的通信 2019年18篇 2018年11篇 目录 目录 分类专栏 算法--理解与应用 7篇 题解 10篇 错排 2篇 DFS 2篇 BFS 1篇 莫队算法 1篇 Leetcode 8篇 小程序 实付元 使用余额支付 点击重新获取 扫码支付 钱包余额 0 抵扣说明： 1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。

2.余额无法直接购买下载，可以购买VIP、C币套餐、付费专栏及课程。

余额充值