2022年2022年广度优先搜索和深度优先搜索 .pdf

有两种常用的方法可用来搜索图：即深度优先搜索和广度优先搜索。它们最终都会到达所有连通的顶点。深度优先搜索通过栈来实现，而广度优先搜索通过队列来实现。深度优先搜索：深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进直到不能再前进（到达叶子节点或受到深度限制）时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。下面图中的数字显示了深度优先搜索顶点被访问的顺序。为了实现深度优先搜索，首先选择一个起始顶点并需要遵守三个规则：(1) 如果可能，访问一个邻接的未访问顶点，标记它，并把它放入栈中。(2) 当不能执行规则1 时，如果栈不空，就从栈中弹出一个顶点。(3) 如果不能执行规则1 和规则 2，就完成了整个搜索过程。广度优先搜索：在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索，本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。在深度优先搜索中，算法表现得好像要尽快地远离起始点似的。相反，在广度优先搜索中，算法好像要尽可能地靠近起始点。它首先访问起始顶点的所有邻接点，然后再访问较远的区域。它是用队列来实现的。下面图中的数字显示了广度优先搜索顶点被访问的顺序。实现广度优先搜索，也要遵守三个规则：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - (1) 访问下一个未来访问的邻接点，这个顶点必须是当前顶点的邻接点，标记它，并把它插入到队列中。(2) 如果因为已经没有未访问顶点而不能执行规则1 时，那么从队列头取一个顶点，并使其成为当前顶点。(3) 如果因为队列为空而不能执行规则2，则搜索结束。BFS是一种 盲目搜寻法 ，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。BFS并不使用 经验法则算法 。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出 的伫列 中。一般的实作里， 其邻居节点尚未被检验过的节点会被放置在一个被称为open的容器中（例如伫列或是链表 ），而被检验过的节点则被放置在被称为closed的容器中。（open-closed表）实作方法1.首先将根节点放入伫列中。2.从伫列中取出第一个节点，并检验它是否为目标。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - o如果找到目标，则结束搜寻并回传结果。o否则将它所有尚未检验过的直接子节点加入伫列中。3.若伫列为空，表示整张图都检查过了亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标” 。4.重复步骤 2。C 的实作广度优先搜索算法：void BFS(VLink G, int v) int w; VISIT(v); /*訪問頂點v*/ visitedv = 1; /*頂點 v 對應的訪問標記置為1*/ ADDQ(Q,v); while(!EMPTYQ(Q) v = DELQ(Q); /*退出隊頭元素v*/ w = FIRSTADJ(G,v); /*求 v 的第 1 個鄰接點。無鄰接點則返回-1*/ while(w != -1) if(visitedw = 0) VISIT(w); /*訪問頂點v*/ ADDQ(Q,w); /*當前被訪問的頂點w 進隊 */ visitedw = 1; /*頂點 w 對應的訪問標記置為1*/ w = NEXTADJ(G,v); /*求 v 的下一個鄰接點。若無鄰接點則返回-1*/ 对图 G=(V,E) 进行广度优先搜索的主算法如下。void TRAVEL_BFS(VLink G, int visited, int n) int i; for(i = 0; i n; i +) visitedi = 0; /* 標記數組賦初值（清零）*/ for(i = 0; i =n0 时 ，0c1g(n)=f(n)=n0时，0=f(n)=n0时，0=c g(n)=f(n) 恒成立 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -