用图论解决迷宫地图问题

简单的介绍

3.2结合图论的迷宫生成算法

3.2.1图的深度优先遍历简介

例如，要遍历上面这个图

采取深度优先算法(从1开始)

准备一个Stack s，预定义三种状态：A未被访问B正准备访问C 已经访问

一、访问1，把它标记为已经访问，然后将于它相邻的并且标记为未被访问的点压入s 中并标记为正准备访问

此时系统状态：

已经被访问的点：1

还没有被访问的点：3 4 6 7 8 9 10

正准备访问的点：2 5 (存放在Stack之中)

二、从Stack中拿出第一个元素2，标记为已经访问，然后将于它相邻的并且标记为未被访问的点压入s 中并标记为正准备访问，如图：

简单的介绍

此时系统状态：

已经被访问的点：1 2

还没有被访问的点：4 6 7 8 9 10

正准备访问的点：3 5 (存放在Stack之中)

三、从Stack中拿出第一个元素3，标记为已经访问，然后将于它相邻的并且标记为未被访问的点压入s 中并标记为正准备访问，如图：

此时系统状态：

已经被访问的点：1 2 3 4

还没有被访问的点：8 9 10

正准备访问的点：7 6 5 (存放在Stack之中)

依此类推，重复上面的动作，直到Stack为空，即所有的点都被访问

最后可能的遍历情况，如图：

3.2.2深度优先遍历之迷宫生成算法

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库用图论解决迷宫地图问题在线全文阅读。