（1）问题描述
在本设计题目中，需要使用不相交集合数据结构（disjoint set data structure）来构造一个NN 的从左上角到右下角只有一条路径的随机迷宫，然后在这一迷宫上执行深度优先搜索。
该设计共包含如下四个部分：
①不相交集合数据结构的设计和实现
不相交集合即对于任意两个集合A 和B，A∩B=ø。不相交集合常可以表示为树，此时两个不相交集合的并的实现很容易，如图所示。不相交集合常可用来根据等价关系对集合进行等价划分。
 
②构建随机迷宫
应用不相交集合构建迷宫的算法简要描述如下：给定一个NN的方格（cells），初始时每个方格的四面都是墙（walls），如图6-58（a）所示，其中的S是迷宫的开始处，F是迷宫的结束处。NN迷宫的N2个方格0，1，…，N2-1 初始时每个方格自己成为一个等价类，即{0}，{1}，…，{N2-1}。生成随机迷宫的方法是随机选择一个内部墙（连接两个相邻方格的墙），如果该内部墙关联的两个相邻的方格属于不同的等价类就将该墙除去，在除去该墙的同时将这两个等价类合并。直到所有的方格都在一个等价类中，就完成了随机迷宫的生成。
 
③寻找迷宫路径
迷宫一旦建立后，将迷宫表示为一个无向图：方格作为图中的顶点，如果两个相邻的方格之间没有墙则两个顶点之间有边。为找到从S到F的一条唯一的路径，在该图上从S处开始出发先深搜索，如果搜索到达了F，则搜索停止。
④将迷宫和路径用图形方式画出
用图形方式将上述算法获得的随机迷宫及其上的最短路径画出。用线段来表示迷宫中的墙，用在每个方格中心的点来表示路径。
（2）课程设计目的
掌握不相交集合结构的实现和使用，掌握图的基本算法，建立集合、等价划分、图、搜索等事物之间如何关联的认识。
（3）基本要求
①不相交集合应用数组进行物理存储。
②在生成随机迷宫时，考虑如何使选取墙的次数尽量少。
③在先深搜索找到路径时，要求找到最短的路径，即记录最短路径上的方格，所以先深搜索过程应该是采用栈的非递归实现。此时，在先深搜索结束时，栈中就存放了最短路径上的方格，而不是先深搜索过程访问的所有方格。
④迷宫和路径的图形显示的实现方式不限制，如可以选择VC，TC 或Java 等。
（4）实现提示
不相交集合可父链数组进行物理存储，先深搜索采用栈的非递归实现可参阅一些资料，这样的资料很多。

you m