数据结构与算法课程设计报告-哈工大-应用不相交集合生成随即迷宫

哈尔滨工业大学课程设计报告

图1-2 N×N的迷宫

（3）寻找迷宫路径算法

迷宫一旦建立后，将迷宫表示为一个无向图：方格作为图中的顶点，如果两个相邻的方格之间没有墙则两个顶点之间有边。为找到从S到F的唯一的路径，在该图上从S处开始出发先深搜索，如果搜索到达了F，则搜索停止。 （4）画出迷宫和路径算法

用图形方式将上述算法获得的随机迷宫及其上的最短路径画出。用线段来表示迷宫中的墙，用在每个方格的中心的点来表示路径。

5

哈尔滨工业大学课程设计报告

2 算法设计

2.1 系统整体思路

使用不相交集合数据结构来构造一个N×N的从左上角到右下角只有一条路径的随机迷宫，然后在这一迷宫上执行深度优先搜索。利用不相交集合应用数组进行物理存储，用先深度搜索找到最短路径，记录下最短路径，最后将随机生成的迷宫和相应的路径显示出来。

2.2 关键数据结构设计

用一个二维数组存储迷宫，用不同的数字表示不同的状态，9表示不可到达的点，1表示墙，0表示通路，5表示顶点。按此方式存储生成的随机迷宫，并根据这样的结构来搜寻最短路径。最后根据这样的迷宫结构画出相应的图形界面。

2.3 构建随机迷宫功能相关算法

2.3.1算法基本思想

①随机选择一条边，判断边连接的顶点，是否在同一子树中，如果是则执行③，如果不是则执行②。

②连通这两个顶点，并把他们任意一个添加到另一个所在的子树中。

③判断起点和终点是否在同一子树中，如果不是则执行①，如果是则退出。 按这个步骤执行程序直至程序退出。 2.3.2算法流程图

开始

随机选择一条边

是 判断边连接的顶点 是否在同一子树中

否 连通这两个顶点并合并两个子树

判断所有顶点 否 是否在同一子树中

是 结束 图2-1 构建随机迷宫算法流程图

6

哈尔滨工业大学课程设计报告

2.4 寻找迷宫路径功能相关算法

2.4.1算法基本思想

迷宫表示为一个无向图：格子作为图中的顶点，如果两个相邻的方格之间没有墙则两个顶点之间有边（在二维数组中用不同数字作为标记）。找到从S到F的唯一的路径，在该图上从S处开始出发先深搜索，利用栈存储每一次回退前由起始点“S”到某点v的路径（链表实现，只需要存储对应二维数组的下标），回退前判断终止点v是否为迷宫重点“F”，如果是，停止搜索，栈中路径即为要求的最短路径，如果不是，栈顶元素出栈，并且依次回退，继续搜索下一条路径，以此类推，直到找最短路径。如果没有找到，则代表迷宫建立出错。 另：这里面迷宫生成时即生成只有一条有效路径到达终点（不重复访问格子的路径），所以寻找路径时找到的第一条即是唯一的一条路径。 2.4.2算法流程图 开始 令v=S（迷宫起点） 标记顶点v，压入栈 令v=n 是 判断v是否有未访问过的邻接顶点n 否 是 判断v是否为迷宫重点F 否 v出栈，回退至上一个顶点

输出栈中内容即为最短路径 结束 图2-2 寻找迷宫路径算法流程图

2.5 画出迷宫和路径功能相关算法

2.5.1算法基本思想

用图形方式将上述算法获得的随机迷宫及其上的最短路径画出。第一部分是画出随机迷宫，给定二维数组，其中有标记格子以及墙的有无，根据二位数组的下标计算出每个位置在显示器中的坐标X，Y，判断数组中内容所对应的是墙还是顶点还是通路，利用java中swing类组件画出相应图形。第二部分画出最短路径，给定栈中存储路径在二维数组中格子的下标，计算出在显示器中的坐标X，Y，由两个顶点中心点的连线表示两点之

7

哈尔滨工业大学课程设计报告

间的路径，利用java中swing类组件画出路径。 2.5.2算法流程图 开始 i=1，j=1 计算相应顶点（i,j）坐标（X,Y） 根据数组内容 在（X,Y）画出相应图形 j++ 是 判断j

图2-3 画出迷宫算法流程图

开始 出栈 计算路径相应坐标 在相应位置画出路径 否 判断栈是否为空 是 结束 图2-4 画出迷宫路径算法流程图

8