过程1、首先将根结点放入队列中。2、从队首取出一个结点，按照产生式规则逐个生成新的结点数据，对新数据：如果如果是目标结点，则结束算法并返回结果。如果不是目标结点，则检查它是否已在搜索树中出现过，未出现就将它作为尚未检查过的子结点加入到队列的队尾（特殊情况下，也有已出现过的结点重新入队的）。3、重复步骤2。4、若队列为空，表示整张图都检查过了，即目标无法达到，结束算法并返回“找不到目标”的信息。算法细化：算法细化1、用哈希数组判断新生成的结点数据是否已出现过。2、队列经常要多开一行，记录新结点的父亲（即该结点由上一层的哪个结点扩展而来），用于最后输出过程。3、如数据规模过大，需要使用循环队列（后果是无法记录父亲）。算法框架：算法框架fu
ctio
creatibegi
caseiof1creat按照第一产生式规则生成新状态数据；2creat按照第二产生式规则生成新状态数据；e
d
fe
dprocedurebfsbegi
joi
起始状态while
ot队空dobegi
当前处理状态deqfori第一产生式规则to最大产生式规则dobegi
新状态creatiif新状态目标状态the
begi
pri
texite
delseif
othaxi新状态the
begi
joi
新状态haxi新状态truee
de
de
de
d空间复杂度：线性队列：O最大可能状态数空间复杂度循环队列：O最大可能状态数2时间复杂度：时间复杂度最差情形下，BFS必须寻找所有到可能结点的所有路径。O最大可能状态数完全性：广度优先搜索算法具有完全性。只要目标存在，则BFS一定会找到。但是，若完全性目标不存在，且问题规模为无限大，则BFS将不收敛（不会结束）。适用范围：广度优先搜索是找到第一个解的算法，即距离根结点的边数最少的解。适用范围如果所有边的权值都相等（即所有产生新状态的代价相同），则这个解也是最优解。例一：将一个马从MN的棋盘的左下角跳到右上角，需要的最少步数是多少？分析：1、用一个121m
的数组作为工作队列，用于存储搜索树。2、使用m
的二维哈希数组判重。3、生成搜索树的同时，记录父节点的序号和新结点的层数。4、最后从目标结点向起始结点回朔，用一个栈存储回朔的中间状态。例二：在一个2
1的一维棋盘上，有
个黑色棋子和
个白色棋子，初始状态如图：●●●●○○○
○
规定棋子移动规则如下：1、如果某棋子的旁边正好为空，这枚棋子可以移动到空位置上。2、如果某棋子的一侧有棋子，二那枚棋子的另一侧为空位置，这枚r