宽度优先搜索算法及其时间、空间复杂度分析

宽度优先搜索算法是沿着树的宽度遍历树的节点，它从深度为0的层开始，直到最深的层次。它可以很容易地用队列实现。例如，考虑图4－2给出的树。这里节点的遍历顺序是按照节点中数字的大小顺序遍历的。

图4-2　宽度优先算法对深度为3的树的遍历顺序

采用队列结构，宽度优先算法可以表示如下：

上面给出的宽度优先搜索算法依赖于简单的原理：如果当前的节点不是目标节点，则把当前节点的子孙以任意顺序增加到队列的后面，并把队列的前端元素定义为current。如果目标发现，则算法终止。

（一）宽度优先搜索的时间复杂度

为了便于分析，我们考虑一棵树，其每个节点的分支系数都为b，最大深度为d。其中分支系数是指一个节点可以扩展产生的新的节点数目。因此搜索树的根节点在第1层会产生b个节点，每个节点又产生b个新的节点，这样在第2层就会有b2个节点。因为目标不会出｜现在深度为（d－l）层，失败搜索的最小节点数目为：

(www.xing528.com)

而在找到目标节点之前可能扩展的最大节点数目为：

对于d层，目标节点可能是第一个状态，也可能是最后一个状态。因此，乎均需要访问的d层节点数目为：（1＋bd）/2。所以，平均总的搜索的节点数目为：

因此，宽度优先搜索的时间复杂度和搜索的节点数目成正比。

（二）宽度优先搜索的空间复杂度

宽度优先搜索中，空间复杂度和时间复杂度一样，需要很大的空间，这是因为树的叶节点都同时需要储存起来。根节点扩展后，队列中有b个节点。第1层的最左边节点扩展后，队列中有（2b－l）个节点。而当d层最左边的节点正在检查是否是目标节点的在队列中的节点数目最多，为（bd）。该算法的空间复杂度和队列长度有关，在最坏的情况下约为指数级O（bd）。

宽度优先搜索是一种盲目搜索^[2]，时间和空间复杂度都比较高，当目标节点距离初较远时（即d较大时）会产生许多无用的节点，搜索效率较低。宽度优先搜索中时间需求是一个很大的问题，特别是当搜索的深度比较大时尤为严重，空间需求是比执行时间更严重的一个问题。

但是宽度优先搜索也有其优点：目标节点如果存在，用宽度优先搜索算法总可以找到该目标节点，而且是d最小（即最短路径）的节点。