广度优先搜索和深度优先搜索

广度优先搜索和深度优先搜索

ID:14717792

大小:155.00 KB

页数:4页

时间:2018-07-30

广度优先搜索和深度优先搜索_第1页
广度优先搜索和深度优先搜索_第2页
广度优先搜索和深度优先搜索_第3页
广度优先搜索和深度优先搜索_第4页
资源描述:

《广度优先搜索和深度优先搜索》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、有两种常用的方法可用来搜索图:即深度优先搜索和广度优先搜索。它们最终都会到达所有连通的顶点。深度优先搜索通过栈来实现,而广度优先搜索通过队列来实现。 深度优先搜索: 深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点,不断地向纵深前进直到不能再前进(到达叶子节点或受到深度限制)时,才从当前节点返回到上一级节点,沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。下面图中的数字显示了深度优先搜索顶点被访问的顺序。为了实现深度优先搜索,首先选择一个起始顶点并需要遵守三个规则:(1)如果可能,访问一个邻接的未访问顶点,标记它,并把

2、它放入栈中。(2)当不能执行规则1时,如果栈不空,就从栈中弹出一个顶点。(3)如果不能执行规则1和规则2,就完成了整个搜索过程。广度优先搜索:在深度优先搜索算法中,是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索,本层的结点没有搜索处理完时,不能对下层结点进行处理,即深度越小的结点越先得到扩展,也就是说先产生的结点先得以扩展处理,这种搜索算法称为广度优先搜索法。在深度优先搜索中,算法表现得好像要尽快地远离起始点似的。相反,在广度优先搜索中,算法好像要尽可能地靠近起始点。它首先访问起始顶点的所有邻接点,然后再访问较远的区域。

3、它是用队列来实现的。下面图中的数字显示了广度优先搜索顶点被访问的顺序。实现广度优先搜索,也要遵守三个规则:(1)访问下一个未来访问的邻接点,这个顶点必须是当前顶点的邻接点,标记它,并把它插入到队列中。(2)如果因为已经没有未访问顶点而不能执行规则1时,那么从队列头取一个顶点,并使其成为当前顶点。(3)如果因为队列为空而不能执行规则2,则搜索结束。BFS是一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位址,彻底地搜索整张图,直到找到结果为止。BFS并不使用经验法则算法。从算法的观点,所有因为展开节点

4、而得到的子节点都会被加进一个先进先出的伫列中。一般的实作里,其邻居节点尚未被检验过的节点会被放置在一个被称为open的容器中(例如伫列或是链表),而被检验过的节点则被放置在被称为closed的容器中。(open-closed表)实作方法1.首先将根节点放入伫列中。2.从伫列中取出第一个节点,并检验它是否为目标。o如果找到目标,则结束搜寻并回传结果。o否则将它所有尚未检验过的直接子节点加入伫列中。2.若伫列为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。3.重复步骤2。C的实作广度优先搜索算法:voidBFS(

5、VLinkG[],intv){intw;VISIT(v);/*訪問頂點v*/visited[v]=1;/*頂點v對應的訪問標記置為1*/ADDQ(Q,v);while(!EMPTYQ(Q)){v=DELQ(Q);/*退出隊頭元素v*/w=FIRSTADJ(G,v);/*求v的第1個鄰接點。無鄰接點則返回-1*/while(w!=-1){if(visited[w]==0){VISIT(w);/*訪問頂點v*/ADDQ(Q,w);/*當前被訪問的頂點w進隊*/visited[w]=1;/*頂點w對應的訪問標記置為1*/}w=NEXTADJ(G,v);

6、/*求v的下一個鄰接點。若無鄰接點則返回-1*/}}}对图G=(V,E)进行广度优先搜索的主算法如下。voidTRAVEL_BFS(VLinkG[],intvisited[],intn){inti;for(i=0;i

7、{f(n)

8、如果存在正常数c1、c2和正整数n0,使得当n>=n0时,0

9、如果存在正常数c和正整数n0,使得当n>=n0时,0<=f(n)<=cg(n)恒成立}  定义三:Ω(g(n))={f(n)

10、如果存在正常数c和正整数n0,使得当n>=n0时,0<=cg(n)<=f(n)恒成立}

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。