馆档网 文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 天文/地理 > 广度优先搜索
侵权投诉

广度优先搜索

(一)深度优先搜索遍历算法

深度优先搜索的过程

深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中,对于最新发现的节点,如果它还有以此为起点而未搜索的边,就沿此边继续搜索下去。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v有那条边的始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被发现为止。即

⒈以给定的某个顶点V0为起始点,访问该顶点;

⒉选取一个与顶点V0相邻接且未被访问过的顶点V1,用V1作为新的起始点,重复上述过程;

⒊当到达一个其所有邻接的顶点都已被访问过的顶点Vi时,就退回到新近被访问过的顶点Vi- 1,继续访问Vi-1尚未访问的邻接点,重复上述搜索过程; ⒋直到从任意一个已访问过的顶点出发,再也找不到未被访问过的顶点为止,遍历便告完成。

这种搜索的次序体现了向纵深发展的趋势,所以称之为深度优先搜索。

深度优先搜索算法描述:

程序实现有两种方式--递归与非递归。 一、递归

递归过程为:

Procedure DEF-GO(step) for i:=1 to max do

if 子结点符合条件 then 产生新的子结点入栈;

if 子结点是目标结点 then 输出 else DEF-GO(step+1); 栈顶结点出栈; endif; enddo; 主程序为: Program DFS; 初始状态入栈; DEF-GO(1);

二、非递归

Program DEF(step); step:=0; repeat

step:=step+1; j:=0;p:=false repeat j:=j+1;

if 结点符合条件 then

第1页

热门文档

相关文档

  • 广度优先搜索

    广度优先搜索_其它_高等教育_教育专区。信息学竞赛精品广度搜索在程序设计中的应用 7.3.2 广度优先搜索广度优先搜索算法: (1)从图中某个未被访问的顶点出发,...

  • 9. 广度优先搜索

    9. 广度优先搜索_专业资料。ACM编程小讲ACM算法与程序设计第九讲 搜索专题广度优先(BFS) 广度优先搜索算法(Breadth -First-Search) ? 也被作宽度优先搜索,或...

  • 广度优先搜索

    广度优先搜索_理学_高等教育_教育专区。bfs程序设计实习 第十八讲 广度优先搜索 内容提要 ? 广度优先搜索的基本思想 ? POJ1077八数码问题 ? 广搜 ? 双向广搜(...

  • 广度优先搜索

    深度越小的结点越先得到扩展, ,即深度越小的结点越先得到扩展,也就是 的结点先得以扩展处理, 说先产生 的结点先得以扩展处理,这种搜 索算法称为广度优先搜索法...

  • 广度优先搜索

    广度优先搜索方法的具体介绍。隐藏>> 广度优先搜索(BFS)算法 宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算 法也是很多重要的图的算法...

  • 广度优先搜索

    广度优先搜索_IT/计算机_专业资料。a广度优先搜索例:重排九宫问题游戏 在一个3乘3的九宫中有1-8的8个数及一个空格随机 摆放在其中的格子里。如下面左图所示...

  • 图的广度优先搜索的应用

    图的广度优先搜索的应用_IT/计算机_专业资料。广度优先搜索的简单应用图的广度优先搜索的应用内容提要广度优先搜索是分层次搜索,广泛应用于求解问题的最短路径、最...

  • 关于广度优先搜索的两个问题

    关于广度优先搜索的两个问题_IT/计算机_专业资料。算法思想关于广度优先搜索的两个问题 (李学武 ,2005 年 1 月) 目录: 一、在广度优先搜索中新结点入队前的判...

  • 广度优先搜索算法

    常用算法——广度优先搜索 4页 2财富值 迷宫算法(经典广度优先搜索... 7页 免费搜你所想,读你所爱 拒绝盗版,营造绿色文库 如要投诉违规内容,请到百度文库...

  • 广度优先搜索1

    广度优先搜索1_教育学/心理学_人文社科_PPT专区。搜索 什么是搜索算法呢? 什么是搜索算法呢?搜索算法是利用计算机的高性能来有目的地 穷举一个问题的部分或所有...

站点地图 | 文档上传 | 侵权投诉 | 手机版
新浪认证  诚信网站  绿色网站  可信网站   非经营性网站备案
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  email
返回顶部