前面一篇文章用jquery制作了一个拼图游戏，这篇文章介绍如何使用广度优先搜索算法来计算完成拼图的方法。
广度优先搜索是图论中最基本的一种遍历方法。以前学数据结构的时候接触过，但是没有真正理解，也从来没有用过，现在遇到这个拼图游戏路径计算问题，才真正知道了什么是广度优先搜索。
首先拿一个2行2列的作为例子，把每个小方格赋上号码，1230是我们的初始状态，目标状态是2013(0代表空白方格)。
|
|
|
由1230找到2013的具体算法如下: 第一步、取到根节点1230的两个子节点1032,1203。 第二步、取出子节点1032，跟目标节点对比，不相同，于是继续向下寻找到节点1032的子节点0132。 第三步、当找到子节点0132以后,有两种选择：1.查看节点1032的子节点0132。2.查看节点1032的兄弟节点1203.如果是第一种选择的话就是深度优先搜索，第二种选择的话就是广度优先搜索。两种搜索的时间复杂度都是相同的，但是我想要得到最短的路径，所以，这里采取广度优先搜索。即选择2。 第四步、取出节点1032的兄弟节点1203。跟目标节点对比，不相同，于是继续向下寻找到节点1203的子节点0213。 第五步、循环第二步。 |
|
将上述算法抽象出来的话，大概是:
1.初始化节点对象，放入存储队列中。
2.获得队列中第一个节点，检验该节点是否为目标节点
是 从遍历队列中倒序寻找父节点，直到道根节点为止，存储在解决方法对列中，跳出
否 将节点加入遍历队列中，获取节点的子节点，加入存储存队列中
3.重复2
关于广度优先搜索如果还有不理解的，可以参考维基百科。
了解了广度优先搜索的算法，如何用编程语言去实现它呢？关键的地方有以下几点：
第一、节点的构造，包括节点的序号，父节点序号，节点数组，节点移动数组。节点的序号不难理解，从根节点开始，下面出现的节点序号都加一。父节点序号就是通过移动转换为当前节点的那个节点的序号(真尼玛绕嘴)。节点数组用来存储节点当前状态。节点移动数组存储节点如何从父节点变换成当前节点的信息(例如:向上移动7号)。这样，当我们找到目标节点以后，就可以往回一步步查看节点是如何移动而来的。
第二、几个队列的意义。存储队列，用来存放已经被检验过的节点。遍历队列，存放未被检验过的节点，遵循先进先出的原则。
第三、取子节点。根据游戏的规则，空白方格可以跟邻接方格互换。所以，只需要查看空白方格即可。按照上左下右的顺序检查是否可以移动，可以移动则生成移动后的节点。移动后的节点并不一定就是子节点，因为还有可能是它的父节点，所以要从存储节点中进行查找，如果找到了该节点说明就是父节点，如果没有找到，该节点就是子节点。
具体实现效果我就不往网站上挂了，因为js会stackoverflow的，如果想要查看代码，你可以点击此处下载。
