




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
计算机算法设计与分析第6章回溯法6.1.1深度优先搜索策略深度优先搜索(Depth-FirstSearch,DFS)策略是一种常用的图遍历搜索算法,用于在图或树结构中搜索特定的目标。基本思想是从起始结点开始,沿着一条路径一直向下搜索,直到无法继续下去,然后回溯到前一个结点,继续搜索其他路径,直到找到目标结点或者尝试了所有可能后确定最优解或确定没有解。深度优先实例ABCDEFABCDEF给定图G=(V,E),创建一个栈,用于存储待访问的结点;创建一个数组,用于存储每个结点访问状态。深度优先搜索策略的基本思想为:(1)初始化:任选一个结点v作为起始结点,将起始结点放入栈中。(2)当栈不为空时,执行以下步骤:①出栈-->当前结点,访问当前结点其标记为已访问。②检查是否为目标结点,若是,则搜索结束,否则继续。③获取当前结点的所有邻居结点。④对于每个邻居结点,如果它未被访问,则将其放入栈中,并将其标记为已访问。(3)重复步骤(2),直到找到目标结点提前结束,或者栈为空且没找到目标结点而搜索失败结束。6.1.1深度优先搜索策略DFS的非递归伪代码DFS(start):beginstack.push(start)//将起始结点加入栈中visited[start]
true//标记相邻结点为已访问whilestackisnotemptydocurrent
stack.pop()//弹出栈顶元素,并用current记录 printcurrent//处理结点ifcurrent=objectthenreturnendif//若为目标结点,搜索结束foreachneighborincurrent.neighborsdo//遍历当前结点的相邻结点ifvisited[current]=falsethen//如果相邻结点未被访问过stack.push(neighbor)//将相邻结点加入栈中 isited[neighbor]
true//标记相邻结点为已访问
endifendforendwhileend初始化,入栈,置访问标记栈非空循环出栈,访问并判断是否为目标对所有邻接点,未访问的入栈,并置访问标记DFS的递归伪代码DFS(start):beginvisited[start]
trueprintstartifstart=objectthen//若为目标结点,搜索结束returnendif
foreachneighborinstart.neighborsthen
ifvisited[neighbor]=falsethen
DFS(neighbor)
endifendforend初始化,入栈,置访问标记对所有邻接点若未访问,则作为新出发点递归时间复杂度采用邻接表存储时,深度优先搜索的时间复杂度为O(|V|+|E|),其中|V|
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 机动车售后服务合同范本
- 美术高考集训班协议合同
- 现场勘测安全协议书模板
- 自建房盖楼出售合同范本
- 腌制品配送服务合同范本
- 鱼缸家用转让协议书模板
- 离婚前财产转移合同范本
- 混凝土施工承包合同协议
- 高压铝电缆收购合同范本
- 潍坊小餐饮加盟合同范本
- 实验室人员授权管理制度
- 2025至2030中国柴油内燃机行业发展趋势分析与未来投资战略咨询研究报告
- 水政执法水行政处罚课件
- 2025贵州省水利投资(集团)有限责任公司招聘84人笔试备考题库附答案详解
- 广东省广州市南沙区2025年八年级下学期期末数学试题及参考答案
- PICC的日常护理课件
- 2025年口腔医学专业毕业考试试题及答案
- 河南省郑州一八联合2025年八下物理期末综合测试试题含解析
- 2025年中学教师资格考试《综合素质》教育热点案例分析题实战解析及答案
- GB/T 45577-2025数据安全技术数据安全风险评估方法
- 中国瓷砖胶行业市场深度调研及发展趋势与投资前景研究报告2025-2028版
评论
0/150
提交评论