在之前的一篇文章(迷宫营救公主算法)中提供了一个半成品的解决方案,之所以说他是半成品,是因为首先选择的算法就不对,采用的是深度优先搜索,其次也没有真正的用对深度优先算法,走过的点应该标记为已经走过,而不应该重复遍历该节点。下面的文章对于广度优先和深度优先两种算法的解释非常到位。今天准备把这个问题再完整的用正确的算法解答一遍。
文章链接:【图论】广度优先搜索和深度优先搜索。
就营救公主的问题而言,这里不再重复描述问题了,请点击这里查看题目分析:链接。这次选用广度优先算法来解决该问题。上面的算法介绍文章中对该算法已经分析得非常清晰了。先给解决本问题的算法伪代码:
这里每个节点有三种状态: