Breadth First Search - 广度优先搜索
问题
在的二维方格图中从点移动到点。
解法
广度优先搜索是优先搜索二维方格图中每个节点的相邻节点，与之相对的深度优先搜索则会沿着节点的一个相邻节点试图走到最远。
例如在下面这个二维方格中从移动到。初始时将起点加入待搜索节点的队列中，之后每次从中取出头节点，访问四周从未被访问的邻节点，并将邻节点加入中。将每个节点加入之前将其染为红色，避免重复访问。
初始时将染红并加入；
从中取出头节点，因，将其四周未被染红的节点染红并加入，图中的左边为头部，右边为尾部，新访问的节点插入队列尾部，每次从队列中取出头节点：
从中取出头节点，因，将其四周未被染红的节点染红并加入；
从中取出头节点，因，其四周的节点都已经被染红，因此不加入任何新节点；
从中取出头节点，因，算法结束；
本章的图搜索中，一个节点通常只需要搜索一次，常用染色来标记一个节点是否被搜索过，染红后就不会再放入待搜索队列中。用类似“父节点”指针来记录搜索时遇到节点的上一个节点，搜索完成时通过“父节点”逆向的找到一条从回到的路径。
该算法的时间复杂度为。