ACM算法设计-BFS广度搜索-DFS入门深度搜索详解省名师优质课获奖课件市赛课一等奖课件.ppt
ACM算法设计-BFS广度搜索-DFS入门深度搜索详解省名师优质课获奖课件市赛课一等奖课件.ppt
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- ACM 算法 设计 BFS 广度 搜索 DFS 入门 深度 详解 名师 优质课 获奖 课件 市赛课 一等奖
- 资源描述：
-
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,本幻灯片资料仅供参考，不能作为科学依据，如有不当之处，请参考专业资料。谢谢,ACM算法设计BFS(广度搜索)-DFS(深度搜索)详解,第1页,BFS算法,by plato,第2页,复习,DFS,算法,思想：一直往深处走，直到找到解或者走不下去为止,框架：,DFS(dep,)/dep,代表当前,DFS,深度,if(,找到解,|,走不下去了,),return;,枚举下一个情况，,DFS(dep+1,),第3页,3,DFS,遍历方式,H,A,L,I,F,B,C,D,E,J,G,K,S,第4页,4,存在其它遍历方式？,第5页,5,BFS,思想,1.,从初始状态,S,开始，利用规则，生成下一层状态。,2.,次序检验下一层全部状态，看是否出现目标状态,G,。,否则就对该层全部状态节点，分别利用规则。生成再下一层全部状 态节点。,3.,继续按上面思想生成再下一层全部状态节点，这么一层一层往下展开。直到出现目标状态为止。,按层次次序来遍历搜索树,第6页,6,BFS,框架,通惯用队列,(,先进先出,FIFO),实现,初始化队列,Q.,Q=,起点,s;,标识,s,为己访问,;,while(Q,非空,),取,Q,队首元素,u;u,出队,;,if(u=,目标状态,),全部与,u,相邻且未被访问点进入队列,;,标识,u,为已访问,;,第7页,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,入口,出口,寻找一条从入口到出口通路,迷宫问题,第8页,8,东,南,北(,上,),西(,左,),前进方向：上(北)、下(南)、左(西)、右(东),首先从下方开始，按照逆时针方向搜索下一步可能前进位置,迷宫问题,-DFS,第9页,9,入口,出口,在迷宫周围加墙，防止判断是否出界,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题,-DFS,第10页,10,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,在寻找出口过程中，每前深入，当前位置入栈；每回退一步，栈顶元素出栈,栈,(1,1),迷宫问题,-DFS,第11页,11,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),向下方前深入,迷宫问题,-DFS,第12页,12,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),i,(3,1),向下方前深入,迷宫问题,-DFS,第13页,13,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(4,1),(3,1),i,向下方前深入,break,迷宫问题,-DFS,第14页,14,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(5,1),(3,1),(4,1),向下方前深入,break,迷宫问题,-DFS,第15页,15,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(6,1),(3,1),(4,1),(5,1),向下方前深入,break,迷宫问题,-DFS,第16页,16,i,i,i,i,i,i,迷宫问题(续),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(7,1),(3,1),(4,1),(5,1),(6,1),向下方前深入,break,第17页,17,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方、右方、左方均不能前进，上方是来路，则后退,栈,(1,1),(2,1),(7,1),(3,1),(4,1),(5,1),(6,1),break,迷宫问题,-DFS,第18页,18,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),向右方、左方均不能前进，下方路不通，上方是来路，则后退,break,迷宫问题,-DFS,第19页,19,i,i,i,i,i,8,1,2,3,4,5,6,7,0,9,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(5,2),向右方前深入,break,迷宫问题,-DFS,第20页,20,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前深入,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(5,3),(5,2),break,迷宫问题,-DFS,第21页,21,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,0,9,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方前深入,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(6,1),(5,2),(5,3),break,迷宫问题,-DFS,第22页,22,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前深入,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(6,4),(5,2),(5,3),(6,3),i,break,迷宫问题,-DFS,第23页,23,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前深入,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(6,5),(5,2),(5,3),(6,3),(6,4),break,迷宫问题,-DFS,第24页,24,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,0,9,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方前深入,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(7,5),(5,2),(5,3),(6,3),(6,4),(6,5),break,迷宫问题,-DFS,第25页,25,i,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,向下方前深入,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(8,5),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),break,迷宫问题,-DFS,第26页,26,i,i,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前深入,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(8,6),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),break,迷宫问题,-DFS,第27页,27,i,i,i,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前深入,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(8,7),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),(8,6),break,迷宫问题,-DFS,第28页,28,i,i,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,下方路不通，向右方前深入，抵达出口,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(8,8),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),(8,6),i,i,(8,7),break,迷宫问题,-DFS,第29页,29,i,i,i,i,i,i,i,i,i,i,i,i,i,i,8,1,2,3,4,5,6,7,9,8,1,2,3,4,5,6,7,0,9,0,用栈保留了路径,栈,(1,1),(2,1),(3,1),(4,1),(5,1),(8,8),(5,2),(5,3),(6,3),(6,4),(6,5),(7,5),(8,5),(8,6),(8,7),迷宫问题,-DFS,第30页,30,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径),-BFS,第31页,31,1,1,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径),-BFS,第32页,32,1,1,2,2,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径),-BFS,第33页,33,1,1,2,2,3,3,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径),-BFS,第34页,34,1,1,2,2,3,4,3,4,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径),-BFS,第35页,35,1,1,2,2,3,4,5,3,4,5,5,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径),-BFS,第36页,36,1,1,2,6,2,3,4,5,3,4,5,6,5,6,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径),-BFS,第37页,37,1,7,1,2,6,7,2,3,4,5,3,4,5,6,5,7,6,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径),-BFS,第38页,38,1,7,8,1,2,6,7,8,2,3,4,5,3,4,5,6,5,7,8,6,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,迷宫问题(最短路径),-BFS,第39页,39,1,7,8,9,1,2,6,7,8,2,3,4,5,3,4,5,6,5,7,8,9,6,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宫问题(最短路径),-BFS,第40页,40,1,7,8,9,1,2,6,7,8,2,3,4,5,10,3,10,4,5,6,10,5,7,8,9,6,10,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宫问题(最短路径),-BFS,第41页,41,1,7,8,9,1,2,6,7,8,2,3,4,5,10,11,3,11,10,11,4,5,6,10,11,5,7,8,9,6,10,11,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宫问题(最短路径),-BFS,第42页,42,1,7,8,9,1,2,6,7,8,12,2,3,4,5,10,11,3,11,10,11,12,4,5,6,10,11,12,5,7,8,9,6,10,12,11,12,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宫问题(最短路径),-BFS,第43页,43,1,7,8,9,13,1,2,6,7,8,12,2,3,4,5,10,11,3,11,10,11,12,4,5,6,10,11,12,13,5,7,8,9,6,10,13,12,11,12,13,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宫问题(最短路径),-BFS,第44页,44,1,7,8,9,13,1,2,6,7,8,12,2,3,4,5,10,11,3,11,10,11,12,4,5,6,10,11,12,13,5,7,8,9,6,10,13,12,11,12,13,入口,出口,借助于队列可求得入口到出口最短路径(若存在),8,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,9,0,9,0,9,迷宫问题(最短路径),-BFS,第45页,45,小结,DFS,：使用,栈,保留未被检测结点，结点按照,深度优先,次序被访问并依次被压入栈中，并以相反次序出栈进行新检测。,类似于树先根遍历,深搜例子：走迷宫，你没有方法用分身术来站在每个走过位置。不撞南山不回头,。,BFS,：使用,队列,保留未被检测结点。结点按照,宽度优先,次序被访问和进、出队列。,类似于树按层次遍历过程,广搜例子,:,你眼镜掉在地上以后，你趴在地板上找。你总是先摸最靠近你地方，假如没有，再摸远一点地方,第46页,46,例题,2,Oil Deposits,题意：给出一个,N,*,M,矩形区域和每个区域状态,-,有,/,没有石油，（定义）假如两个有石油区域是相邻（水平、垂直、斜）则认为这是属于同一个,oil pocket,。,求这块矩形区域一共有多少,oil pocket,。,第47页,47,思绪：,对于每个有油区域，找出全部与它同属一个,oil pocket,有油区域，最终计算一共有多少个,oil pocket,。,？怎样去找出全部与它同属一个,oil pocket,BFS,：找到一个起点；,从这个点出发，枚举四面寻找有油区域；,顺序从找到新区域出发，循环上述过程，直到没有新区域加入。,？怎样去标志同属一个,oil pocket,有油区域,设置一个访问标志代表此区域有没有被包含过，这么话调用,BFS,次数就,=oil pocket,数目。,当然,DFS,也是能够这么做。,FloodFill,第48页,48,框架：,Void BFS(int i,int j),初始化队列,Q,；,while(Q,不为空）,取出队首元素,u;,枚举元素,u,相邻区域，,if(,此区域有油,),入队,;,访问标识,;,Int main(),枚举全部区域，,if(,此区域有油,&,没有被访问过,),BFS(,),第49页,49,练习,:8080/judge/contest/view.action?cid=17535#overview,密码：,123456,第50页,50,推荐书籍,第51页,51,展开阅读全文
咨信网温馨提示：1、咨信平台为文档C2C交易模式，即用户上传的文档直接被用户下载，收益归上传人（含作者）所有；本站仅是提供信息存储空间和展示预览，仅对用户上传内容的表现方式做保护处理，对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿，我们不确定上传用户享有完全著作权，根据《信息网络传播权保护条例》，如果侵犯了您的版权、权益或隐私，请联系我们，核实后会尽快下架及时删除，并可随时和客服了解处理情况，尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确)，网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据，个别因单元格分列造成显示页码不一将协商解决，平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺，下载前须认真查看，确认无误后再购买，务必慎重购买；若有违法违纪将进行移交司法处理，若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传，付费前请自行鉴别，如您付费，意味着您已接受本站规则且自行承担风险，本站不进行额外附加服务，虚拟产品一经售出概不退款（未进行购买下载可退充值款），文档一经付费（服务费）、不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印，是因预览和防盗链等技术需要对页面进行转换压缩成图而已，我们并不对上传的文档进行任何编辑或修改，文档下载后都不会有水印标识（原文档上传前个别存留的除外），下载后原文更清晰；试题试卷类文档，如果标题没有明确说明有答案则都视为没有答案，请知晓；PPT和DOC文档可被视为“模板”，允许上传人保留章节、目录结构的情况下删减部份的内容；PDF文档不管是原文档转换或图片扫描而得，本站不作要求视为允许，下载前可先查看【教您几个在下载文档中可以更好的避免被坑】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用；网站提供的党政主题相关内容(国旗、国徽、党徽－－等)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
6、文档遇到问题，请及时联系平台进行协调解决，联系【微信客服】、【QQ客服】，若有其他问题请点击或扫码反馈【服务填表】；文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“【版权申诉】”，意见反馈和侵权处理邮箱：1219186828@qq.com；也可以拔打客服电话：0574-28810668；投诉电话：18658249818。
实名认证
平台协调中心【客服】
相似文档
自信AI助手
自信AI助手
初中诗歌鉴赏专题复习省名师优质课赛课获奖课件市赛课一等奖课件.ppt
9怀特森先生的课市名师优质课比赛一等奖市公开课获奖课件.pptx
ESI(基本科学指贝葱玛)使用指南市公开课获奖课件省名师优质课赛课一等奖课件.ppt
中学生带手机的利与弊市公开课获奖课件省名师优质课赛课一等奖课件.ppt
中心小学校园文化建设规划名师优质课获奖市赛课一等奖课件.ppt
class-13-定语从句的翻译-英汉翻译市公开课获奖课件省名师优质课赛课一等奖课件.ppt
中学作文细节描写-课件省名师优质课赛课获奖课件市赛课百校联赛优质课一等奖课件.ppt
中学体育教研—邵省名师优质课赛课获奖课件市赛课百校联赛优质课一等奖课件.ppt
中小学校综合办公系统(校园OA)简介分析省名师优质课获奖课件市赛课一等奖课件.ppt
微信客服
客服QQ
发送邮件
意见反馈
链接地址：https://www.zixin.com.cn/doc/6472629.html