Disjoint Set, Union-Find Maze generation

[power_computer]

Hello all,

I am given a project and would like some help/guidance from the community. I am not asking for any code just a direction and little advice on how to approach this project or how these things work per-say. I am behind in my classes due to me having missed 2-3 weeks of classes because of a broken bone prohibiting mobility.

The project description:

I am to design a program that will generate a random maze.
My implementation should do the following. View the maze as a grid of cells
where each cell is enclosed by four walls separating it from all adjoining cells

Me: Hence why they are called disjoint sets?

Continue randomly removing walls between two cells not currently joined by a path until all cells are reachable from every other cell. Then randomly select on one edge of the maze and a cell on the opposing edge to be the entrance and exit.

I must implement a Union-Find class which uses a forest of trees formed by the partition of a set via the parent pointer array implementation. I must utilize the weighted union rule and path compression.

Here I am assuming the grid is a 2D array i.e rows and columns, quit obviously.

So far by doing some researching on google I was able to find a C++ implementation of a disjoint data structure class

http://www.emilstefanov.net/Projects/DisjointSets.aspx

My problem is 1. I do not like using/copying someone else's work because I don't feel like I learned anything 2. This class doesn't seem to fit my project approach it is looking for I am not familiar with the C++ STL vector class.

So on the agenda is to create a Union-Find class using the weighted union rule and path compression. Once this is created I should test the class by using 2-3 trees and testing the weighted union rule and path compression rule. How could I test these? If one tree has 3 children and another has 1 child the union rule will go to the larger tree? and Path compression when I union two trees together all children(elements) will point to the parent/root node?

Secondly, create a grid of cells, easily done.

At this exact moment I am confused on the maze generation algorithm
What exactly is meant by the parent pointer array method?
Each cell has its own parent pointer until that cell is randomly selected along with another to be unioned together? I see many complications with my thought process on how to design and implement a proper algorithm

Also what is the forest of trees exactly to be in this case? Each cell being a root node and the adjoining walls being its children?

Sorry for the mass confusion fellow programmers. And Yes I have searched this forum for similar posts however, many of them not being recent I can't or do not want to post in them. I just have few questions, well many, too ask :). I hope not to be too bothersome :(

[lessonlearned]

<<Flaming removed>>

[power_computer]

You are an obvious failure kid.

[VernonDozier]

Tackle the math first. You need to understand the algorithm first. That's an algorithm problem, not a programing problem. It's also pencil-paper or better yet, whiteboard since you'll be erasing a lot. Two cells are disjoint if you can't get from one to another. The trivial way to do this is to knock down all walls. I imagine there's a stipulation that two cells can have exactly one path between them (i.e. no cycles).

I think you need to refine your questions. They are too broad. IMO the only way to answer them is to explain the entire process from the start, which would be time-consuming and they have already been written up at least as well as people here would explain them. Again, I would go the paper and pencil route, figure out what's going on, then try the programming. Also, don't get too bogged down on the math terminology. What works works. You have two disjoint sets and you connect them into one set. Whether the bigger set turns into the smaller set or vice versa is likely irrelevant. You keep knocking down walls till you have ONE set that every cell is a part of.