概述
广度优先算法也是一种图的遍历(挨个访问)算法。像在线性表中那样,在图 如果我们有这种挨个访问每个节点的能力,我们就具有了搜索的能力。这就是广度优先算法。
我在这里用ncurses字符图形库写成了一个广度优先算法的示例程序, ncurses部分的代码内容在深度优先算法里面有详细的解释。这里先粗略的感受一下广度优先算法的逻辑
广度优先算法
深度优先算法
它并不像深度优先算法那样,在一个方向上深入下去,直到某种情况(例如:碰到墙壁)发生之后, 递归上升。 它是由点及面,然后处理面上各点,各点再由点及面这样进行下去。 它借助了队列这种数据结构达成处理的目的,它是怎样借助的可以由看代码直接感受到。
我这里没有考虑没有出口的情况下,广度优先算法的行为结果。之后会有专门的研究文章。
算法过程
首先我说,我们有一个队列(对,我说有就有)。然后我们再来看一个坐标系:
此时A位于坐标(1,1),再走一步(单位长度)它可以到达的点是(1,2)和(2,1) 图中用‘#’进行了标定。我们先把第一个点(1,1)入队,队头指针指向它
我们以 右、下、左、上这样的顺序去考虑这个问题, 让A移动到(1,2)这个位置:
此时A可以一步到达的坐标是(1,3)和(2,2),我们让这两个坐标先后分别入队
我们考虑完了 以A(1,1)点为基础点,向右一步的情况,我们再考虑以(1, 1)为基础点,向下一步的情况 如图:
此时A可以一步到达的坐标是(3,1)和(2,2), 但是(2,2)我们已经在之前的过程中考虑过了,所以我们不应该重复访问。所以之后我们写代码需要一个标记数组。来标记这个点已经处理过。在这里 我们让(3,1)这个坐标入队
显然A(1,1)不能往左边或者上边走。所以这两种情况这里就在这里不考虑了
以上就是我所谓以点及面。
那现在的情况是什么? 现在队列里面已经不仅仅是一个点的坐标了。有好几个点的坐标等待处理,而我们只需要把队头指针向后移动,挨个处理队头指针指向的点。我们就可以处理完所有的点了。
有点像是把二维的每个点推到了一个一维的情况下,然后处理一维的情况,处理面中各点
代码
因为之前我已经有过对于迷宫程序的介绍,这里, 所以现在我只对寻路这部分进行剖析。
|
|
总结
不管是深度优先算法还是广度优先算法,只要有了切身体会,代码实践。它们都是也只是非常简单有趣的算法内容。