几种常用的深度优先搜索算法

Ⅰ 什么是深度优先搜索

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束.
事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次.
在我们遇到的一些问题当中，有些问题我们不能够确切的找出数学模型，即找不出一种直接求解的方法，解决这一类问题，我们一般采用搜索的方法解决。搜索就是用问题的所有可能去试探，按照一定的顺序、规则，不断去试探，直到找到问题的解，试完了也没有找到解，那就是无解，试探时一定要试探完所有的情况（实际上就是穷举）； 对于问题的第一个状态，叫初始状态，要求的状态叫目标状态。 搜索就是把规则应用于实始状态，在其产生的状态中，直到得到一个目标状态为止。 产生新的状态的过程叫扩展（由一个状态，应用规则，产生新状态的过程） 搜索的要点：（1）初始状态； （2）重复产生新状态； （3）检查新状态是否为目标，是结束，否转（2）； 如果搜索是以接近起始状态的程序依次扩展状态的，叫宽度优先搜索。 如果扩展是首先扩展新产生的状态，则叫深度优先搜索。 深度优先搜索 深度优先搜索用一个数组存放产生的所有状态。 （1） 把初始状态放入数组中，设为当前状态； （2） 扩展当前的状态，产生一个新的状态放入数组中，同时把新产生的状态设为当前状态； （3） 判断当前状态是否和前面的重复，如果重复则回到上一个状态，产生它的另一状态； （4） 判断当前状态是否为目标状态，如果是目标，则找到一个解答，结束算法。 （5） 如果数组为空，说明无解。 对于pascal语言来讲，它支持递归，在递归时可以自动实现回溯（利用局部变量）所以使用递归编写深度优先搜索程序相对简单，当然也有非递归实现的算法。 搜索是人工智能中的一种基本方法，是一项非常普遍使用的算法策略，能够解决许许多多的常见问题，在某些情况下我们很难想到高效的解法时，搜索往往是可选的唯一选择。按照标准的话来讲：搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。 搜索虽然简单易学易于理解，但要掌握好并写出速度快效率高优化好的程序却又相当困难，总而言之，搜索算法灵活多变，一般的框架很容易写出，但合适的优化却要根据实际情况来确定。在搜索算法中，深度优先搜索（也可以称为回溯法）是搜索算法里最简单也最常见的，今天我们就从这里讲起，下面的内容假设读者已经知道最基本的程序设计和简单的递归算法。

这是我找的资料，希望能帮到你~~

Ⅱ 简述深度优先搜索遍历的方法。

简述深度优先搜索遍历的方法？深度优先搜索算法(Depth-First-Search, DFS)，最初是一种用于遍历或搜索树和图的算法，在LeetCode中很常见，虽然感觉不难，但是理解起来还是有点难度的。

简要概括，深度优先的主要思想就是“不撞南墙不回头”，“一条路走到黑”，如果遇到“墙”或者“无路可走”时再去走下一条路。

思路
假如对树进行遍历，沿着树的深度遍历树的节点，尽可能深的搜索树的分支，当达到边际时回溯上一个节点再进行搜索。如下图的一个二叉树。


首先给出这个二叉树的深度优先遍历的结果(假定先走左子树)：1->2->4->5->3->6->7

那是怎样得到这样的结果呢？
根据深度优先遍历的概念：沿着这树的某一分支向下遍历到不能再深入为止，之后进行回溯再选定新的分支。

定义节点

class TreeNode{
int val;
TreeNode left;
TreeNode right;
}
递归的方式

分别对左右子树进行递归，一直到底才进行回溯。如果不了解递归可以参考我的博客你真的懂递归吗？。

class Solution{
public void (TreeNode root){
if(root == null){
return;
}
System.out.print(root.val +"->");
(root.left);
(root.right);
}
}
迭代的方式

上面实现了递归方式的深度优先遍历，也可以利用栈把递归转换为迭代的方式。

但是为了保证出栈的顺序，需要先压入右节点，再压左节点。

class Solution{
public void (TreeNode root){
if(root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
System.out.print(node.val + "->");
if(node.right != null){
stack.push(node.right);
}
if(node.left != null){
stack.push(node.left);
}
}
}
}
接着再列举个利用深度优先遍历的方式的题目

扫雷
给定一个表示游戏板的二维字符矩阵，'M'表示一个未挖出的地雷，'E'表示一个未挖出的空方块，'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻，'X' 则表示一个已挖出的地雷。

根据以下规则，返回相应位置被点击后对应的面板：

如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为'X'。
如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的方块都应该被递归地揭露。
如果一个至少与一个地雷相邻的空方块（'E'）被挖出，修改它为数字（'1'到'8'），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回面板。
示例

输入:

[['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'M', 'E', 'E'],
['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

输出:

[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
思路：根据给定的规则，当给定一个Click坐标，当不为雷的时候以此坐标为基点向四周8个方向进行深度遍历，把空格E填充为B，并且把与地雷M相连的空方块标记相邻地雷的数量。

注意 ：



在这个题中可以沿着8个方向递归遍历，所有要注意程序中，采用了两个for循环可以实现向8个方向递归。

Ⅲ 深度优先法(DFS)算法

深度优先法：O(n+e)是指在图形中，如果以顶点v作为起始开始查找，我们从顶点v的邻接列表选择一个未查找过的顶点w，由定点w继续进行深度优先法的查找，没查找一个顶点，便把该顶点存放在堆栈。知道查找到已经没有任何邻接未遍历的顶点u，此时回到取出堆栈中的顶点，回到上一层顶点继续查找未遍历的顶点，知道所有的顶点皆查找过为止。over~!

Ⅳ 基本算法——深度优先搜索（DFS）和广度优先搜索（BFS）

        深度优先搜索和广度优先搜索，都是图形搜索算法，它两相似，又却不同，在应用上也被用到不同的地方。这里拿一起讨论，方便比较。

一、深度优先搜索

        深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

基本步奏

（1）对于下面的树而言，DFS方法首先从根节点1开始，其搜索节点顺序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中优先选择左分枝）。

（2）从stack中访问栈顶的点；

（3）找出与此点邻接的且尚未遍历的点，进行标记，然后放入stack中，依次进行；

（4）如果此点没有尚未遍历的邻接点，则将此点从stack中弹出，再按照（3）依次进行；

（5）直到遍历完整个树，stack里的元素都将弹出，最后栈为空，DFS遍历完成。

二、广度优先搜索

        广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历算法这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。

基本步奏

（1）给出一连通图，如图，初始化全是白色（未访问）；

（2）搜索起点V1（灰色）；

（3）已搜索V1（黑色），即将搜索V2，V3，V4（标灰）；

（4）对V2，V3，V4重复以上操作；

（5）直到终点V7被染灰，终止；

（6）最短路径为V1，V4，V7.

Ⅳ 大数据最常用的算法有哪些

奥地利符号计算研究所(Research Institute for Symbolic Computation，简称RISC)的Christoph Koutschan博士在自己的页面上发布了一篇文章，提到他做了一个调查，参与者大多数是计算机科学家，他请这些科学家投票选出最重要的算法，以下是这次调查的结果，按照英文名称字母顺序排序。

大数据等最核心的关键技术：32个算法

1、A* 搜索算法——图形搜索算法，从给定起点到给定终点计算出路径。其中使用了一种启发式的估算，为每个节点估算通过该节点的最佳路径，并以之为各个地点排定次序。算法以得到的次序访问这些节点。因此，A*搜索算法是最佳优先搜索的范例。

2、集束搜索(又名定向搜索，Beam Search)——最佳优先搜索算法的优化。使用启发式函数评估它检查的每个节点的能力。不过，集束搜索只能在每个深度中发现最前面的m个最符合条件的节点，m是固定数字——集束的宽度。

3、二分查找(Binary Search)——在线性数组中找特定值的算法，每个步骤去掉一半不符合要求的数据。

4、分支界定算法(Branch and Bound)——在多种最优化问题中寻找特定最优化解决方案的算法，特别是针对离散、组合的最优化。

5、Buchberger算法——一种数学算法，可将其视为针对单变量最大公约数求解的欧几里得算法和线性系统中高斯消元法的泛化。

6、数据压缩——采取特定编码方案，使用更少的字节数(或是其他信息承载单元)对信息编码的过程，又叫来源编码。

7、Diffie-Hellman密钥交换算法——一种加密协议，允许双方在事先不了解对方的情况下，在不安全的通信信道中，共同建立共享密钥。该密钥以后可与一个对称密码一起，加密后续通讯。

8、Dijkstra算法——针对没有负值权重边的有向图，计算其中的单一起点最短算法。

9、离散微分算法(Discrete differentiation)。

10、动态规划算法(Dynamic Programming)——展示互相覆盖的子问题和最优子架构算法

11、欧几里得算法(Euclidean algorithm)——计算两个整数的最大公约数。最古老的算法之一，出现在公元前300前欧几里得的《几何原本》。

12、期望-最大算法(Expectation-maximization algorithm，又名EM-Training)——在统计计算中，期望-最大算法在概率模型中寻找可能性最大的参数估算值，其中模型依赖于未发现的潜在变量。EM在两个步骤中交替计算，第一步是计算期望，利用对隐藏变量的现有估计值，计算其最大可能估计值;第二步是最大化，最大化在第一步上求得的最大可能值来计算参数的值。

13、快速傅里叶变换(Fast Fourier transform，FFT)——计算离散的傅里叶变换(DFT)及其反转。该算法应用范围很广，从数字信号处理到解决偏微分方程，到快速计算大整数乘积。

14、梯度下降(Gradient descent)——一种数学上的最优化算法。

15、哈希算法(Hashing)。

16、堆排序(Heaps)。

17、Karatsuba乘法——需要完成上千位整数的乘法的系统中使用，比如计算机代数系统和大数程序库，如果使用长乘法，速度太慢。该算法发现于1962年。

18、LLL算法(Lenstra-Lenstra-Lovasz lattice rection)——以格规约(lattice)基数为输入，输出短正交向量基数。LLL算法在以下公共密钥加密方法中有大量使用：背包加密系统(knapsack)、有特定设置的RSA加密等等。

19、最大流量算法(Maximum flow)——该算法试图从一个流量网络中找到最大的流。它优势被定义为找到这样一个流的值。最大流问题可以看作更复杂的网络流问题的特定情况。最大流与网络中的界面有关，这就是最大流-最小截定理(Max-flow min-cut theorem)。Ford-Fulkerson 能找到一个流网络中的最大流。

20、合并排序(Merge Sort)。

21、牛顿法(Newton’s method)——求非线性方程(组)零点的一种重要的迭代法。

22、Q-learning学习算法——这是一种通过学习动作值函数(action-value function)完成的强化学习算法，函数采取在给定状态的给定动作，并计算出期望的效用价值，在此后遵循固定的策略。Q-leanring的优势是，在不需要环境模型的情况下，可以对比可采纳行动的期望效用。

23、两次筛法(Quadratic Sieve)——现代整数因子分解算法，在实践中，是目前已知第二快的此类算法(仅次于数域筛法Number Field Sieve)。对于110位以下的十位整数，它仍是最快的，而且都认为它比数域筛法更简单。

24、RANSAC——是“RANdom SAmple Consensus”的缩写。该算法根据一系列观察得到的数据，数据中包含异常值，估算一个数学模型的参数值。其基本假设是：数据包含非异化值，也就是能够通过某些模型参数解释的值，异化值就是那些不符合模型的数据点。

25、RSA——公钥加密算法。首个适用于以签名作为加密的算法。RSA在电商行业中仍大规模使用，大家也相信它有足够安全长度的公钥。

26、Sch?nhage-Strassen算法——在数学中，Sch?nhage-Strassen算法是用来完成大整数的乘法的快速渐近算法。其算法复杂度为：O(N log(N) log(log(N)))，该算法使用了傅里叶变换。

27、单纯型算法(Simplex Algorithm)——在数学的优化理论中，单纯型算法是常用的技术，用来找到线性规划问题的数值解。线性规划问题包括在一组实变量上的一系列线性不等式组，以及一个等待最大化(或最小化)的固定线性函数。

28、奇异值分解(Singular value decomposition，简称SVD)——在线性代数中，SVD是重要的实数或复数矩阵的分解方法，在信号处理和统计中有多种应用，比如计算矩阵的伪逆矩阵(以求解最小二乘法问题)、解决超定线性系统(overdetermined linear systems)、矩阵逼近、数值天气预报等等。

29、求解线性方程组(Solving a system of linear equations)——线性方程组是数学中最古老的问题，它们有很多应用，比如在数字信号处理、线性规划中的估算和预测、数值分析中的非线性问题逼近等等。求解线性方程组，可以使用高斯—约当消去法(Gauss-Jordan elimination)，或是柯列斯基分解( Cholesky decomposition)。

30、Strukturtensor算法——应用于模式识别领域，为所有像素找出一种计算方法，看看该像素是否处于同质区域( homogenous region)，看看它是否属于边缘，还是是一个顶点。

31、合并查找算法(Union-find)——给定一组元素，该算法常常用来把这些元素分为多个分离的、彼此不重合的组。不相交集(disjoint-set)的数据结构可以跟踪这样的切分方法。合并查找算法可以在此种数据结构上完成两个有用的操作：

查找：判断某特定元素属于哪个组。

合并：联合或合并两个组为一个组。

32、维特比算法(Viterbi algorithm)——寻找隐藏状态最有可能序列的动态规划算法，这种序列被称为维特比路径，其结果是一系列可以观察到的事件，特别是在隐藏的Markov模型中。

以上就是Christoph博士对于最重要的算法的调查结果。你们熟悉哪些算法?又有哪些算法是你们经常使用的?

Ⅵ 深度优先搜索算法

这些书上都有很多例子的啊，你可以好好看看。
树的特点，是两个结点间都存着一个路径，从每个结点都可以访问到其它的结点。

一般对于树进行深度优先算法，是从根开始，依次访问当前结点相邻的一个结点。按深度遍历，对于每一个结点都不重复的访问到，直到所有结点被访问。

如二叉树，可以以先根遍历来进行。当达到分枝结点没有所要搜索的结果时，回溯到上一层结点，继续选择相邻的路径进行搜索，一直穷举到结束，如果没有找到，则是无解。

算法很多，代码就不写了。思路明白了，怎么写都行。

Ⅶ 深度优先搜索的系统算法

所有的搜索算法从其最终的算法实现上来看，都可以划分成两个部分──控制结构和产生系统。正如前面所说的，搜索算法简而言之就是穷举所有可能情况并找到合适的答案，所以最基本的问题就是罗列出所有可能的情况，这其实就是一种产生式系统。
我们将所要解答的问题划分成若干个阶段或者步骤，当一个阶段计算完毕，下面往往有多种可选选择，所有的选择共同组成了问题的解空间，对搜索算法而言，将所有的阶段或步骤画出来就类似是树的结构（如图）。
从根开始计算，到找到位于某个节点的解，回溯法（深度优先搜索）作为最基本的搜索算法，其采用了一种“一只向下走，走不通就掉头”的思想（体会“回溯”二字），相当于采用了先根遍历的方法来构造搜索树。
上面的话可能难于理解，没关系，我们通过基本框架和例子来阐述这个算法，你会发现其中的原理非常简单自然。

Ⅷ 深度优先搜索和广度优先搜索、A星算法三种算法的区别和联系

1、何谓启发式搜索算法
在说它之前先提提状态空间搜索.状态空间搜索,如果按专业点的说法就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程.通俗点说,就是 在解一个问题时,找到一条解题的过程可以从求解的开始到问题的结果（好象并不通俗哦）.由于求解问题的过程中分枝有很多,定性,不完备性造成的,使得求解的路径很多这就构成了一个图,我们说这个图就是状态空间.问题的求解实际上就是在这个图中找到一条路径可以从开始到结果.这个寻找的过程就是状态空间搜索.
常用的状态空间搜索有深度优先和广度优先.广度优先是从初始状态一层一层向下找,直到找到目标为止.深度优先是按照一定的顺序前查找完一个分支,再查找另一个分支,以至找到目标为止.这两种算法在数据结构书中都有描述,可以参看这些书得到更详细的解释.
前面说的广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举.这在状态空间不大的情况下是很合适的算法,可是当状态空间十分大,且不预测的情况下就不可取了.他的效率实在太低,甚至不可完成.在这里就要用到启发式搜索了.
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标.这样可以省略大量无畏的搜索路径,提 到了效率.在启发式搜索中,对位置的估价是十分重要的.采用了不同的估价可以有不同的效果.我们先看看估价是如何表示的.
启发中的估价是用估价函数表示的,如：
f(n) = g(n) + h(n)
其中f(n) 是节点n的估价函数,g(n)实在状态空间中从初始节点到n节点的实际代价,h(n)是从n到目标节点最佳路径的估计代价.在这里主要是h(n)体现了搜 索的启发信息,因为g(n)是已知的.如果说详细点,g(n)代表了搜索的广度的优先趋势.但是当h(n) >> g(n)时,可以省略g(n),而提高效率.这些就深了,不懂也不影响啦!我们继续看看何谓A*算法.
2、初识A*算法
启发式搜索其实有很多的算法,比如：局部择优搜索法、最好优先搜索法等等.当然A*也是.这些算法都使用了启发函数,但在具体的选取最佳搜索节点时的 策略不同.象局部择优搜索法,就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点,父亲节点,而一直得搜索下去.这种搜索的结果很明显,由于舍弃了 其他的节点,可能也把最好的节点都舍弃了,因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳.最好优先就聪明多了,他在搜索时,便没有舍弃节点 （除非该节点是死节点）,在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”.这样可以有效的防止“最佳节点”的丢失.那么 A*算法又是一种什么样的算法呢?其实A*算法也是一种最好优先的算法.只不过要加上一些约束条件罢了.由于在一些问题求解时,我们希望能够求解出状态空 间搜索的最短路径,也就是用最快的方法求解问题,A*就是干这种事情的!我们先下个定义,如果一个估价函数可以找出最短的路径,我们称之为可采纳性.A* 算法是一个可采纳的最好优先算法.A*算法的估价函数可表示为：
f'(n) = g'(n) + h'(n)
这里,f'(n)是估价函数,g'(n)是起点到终点的最短路径值,h'(n)是n到目标的最断路经的启发值.由于这个f'(n)其实是无法预先知道 的,所以我们用前面的估价函数f(n)做近似.g(n)代替g'(n),但 g(n)>=g'(n)才可（大多数情况下都是满足的,可以不用考虑）,h(n)代替h'(n),但h(n)

Ⅸ DFS(深搜)算法

深度优先搜索算法(Depth-First-Search) :是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。

话说大诗人李白，一生好饮。幸好他从不开车。

一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：

无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。

这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。

请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。

注意：通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。

答案：14

小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!
站在台阶前，他突然又想着一个问题：
如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？
请你利用计算机的优势，帮助小明寻找答案。

要求提交的是一个整数。
注意：不要提交解答过程，或其它的辅助说明文字。

Ⅹ 深度优先搜索和广度优先搜索的区别。 请讲的详细点，最好能用例子，谢谢啦

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

深度优先搜索基本算法如下{递归算法}：
PROCEDURE dfs_try(i);
FOR i:=1 to maxr DO
BEGIN
IF 子结点 mr 符合条件 THEN
BEGIN
产生的子结点mr入栈；
IF 子结点mr是目标结点
THEN 输出
ELSE dfs_try(i+1);
栈顶元素出栈;
END;
END; 宽度优先搜索算法（又称广度优先搜索算法）是最简单的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijksta单源最短路径算法和Prim最小生成树算法都采用了与宽度优先搜索类似的思想。
宽度优先搜索的核心思想是：从初始结点开始，应用算符生成第一层结点，检查目标结点是否在这些后继结点中，若没有，再用产生式规则将所有第一层的结点逐一扩展，得到第二层结点，并逐一检查第二层结点中是否包含目标结点。若没有，再用算符逐一扩展第二层所有结点……，如此依次扩展，直到发现目标结点为止。

宽度优先搜索基本算法如下：
list[1]:=source; {加入初始结点，list为待扩展结点的表}
head:=0; {队首指针}
foot:=1; {队尾指针}
REPEAT
head:=head+1;
FOR x:=1 to 规则数 DO
BEGIN
根据规则产生新结点nw;
IF not_appear(nw,list) THEN {若新结点队列中不存在，则加到队尾}
BEGIN
foot:=foot+1;
list[foot]:=nw;
list[foot].father:=head;
IF list[foot]=目标结点 THEN 输出；
END；
END；
UNTIL head>foot; {队列为空表明再无结点可扩展}
望采纳