广度优先搜索(6)

6. j:=j+1;

7. New=Expand(Track[dep],j); 8. if New 符合条件 then [

9. 产生子节点New并将其压栈;

10. If 子节点New=target then 更新最优值并出栈 11. else brk:=true; 12. ]

13. else if j>=规则数 then Backtracking 14. else brk:=false; 15. Until brk=true 16. Until dep=0;

两种方式本质上是等价，但两者也时有区别的。 1． 递归方式实现简单，非递归方式较之比较复杂；

递归方式需要利用栈空间，如果搜索量过大的话，可能造成栈溢出，所以在栈空间无法满足的情况下，选用非递归实现方式较好。

（二）广度优先搜索遍历算法

一．宽度优先搜索的过程

宽度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。

宽度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点 ，如此依次扩展，检查下去，直到发现目标节点为止。即

⒈从图中的某一顶点V0开始，先访问V0；

⒉访问所有与V0相邻接的顶点V1，V2，......，Vt；

⒊依次访问与V1，V2，......，Vt相邻接的所有未曾访问过的顶点； ⒋循此以往，直至所有的顶点都被访问过为止。

这种搜索的次序体现沿层次向横向扩长的趋势，所以称之为广度优先搜索。

二、广度优先搜索算法描述：

Program Bfs；

初始化，初始状态存入OPEN表；

队列首指针head:=0;尾指针tail:=1； repeat

指针head后移一位，指向待扩展结点；

for I=1 to max do {max为产生子结点的规则数} begin

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科广度优先搜索(6)全文阅读和word下载服务。