算法设计与分析 课件 第六章 回溯法6.1.1 DFS思想_第1页
已阅读1页，还剩6页未读， 继续免费阅读

付费下载

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

计算机算法设计与分析第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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论