Kruskal's Algorithm (Maze Solving application)
I've been working on generating mazes using a variety of techniques. I have successfully implemented the DFS and Prim's algorithm. I'm currently encountering difficulty implementing Kruskal's algorithm. This is mostly due to my lack of understanding pertaining to union-find algorithms.
I've posted code for 1 successful implementation and then the implementation I am currently working on. Thanks for the help in advance.
Here is what I implemented for Prim's Algorithm:
import java.util.*;
import java.awt.*;
class PrimsFirstTryextends Generator{
//Algorithm referenced in http://www.mazeworks.com/mazegen/maze_faq
//Grows a single tree + keeps track of visited, adjacent, and unvisited squares
PrimsFirstTry(){
super();
GeneratePrims();
}
PrimsFirstTry(int row,int col){
super(row, col);
GeneratePrims();
}
privatevoid GeneratePrims(){
Set in=new HashSet();
Set frontier =new HashSet();
Set out =new HashSet();
for(int count = 0; count< rows; count++){
for (int count2= 0; count2<cols; count2++){
out.add(new Point(count, count2));
}
}
Point frcurrentCell =new Point((int)(Math.random()*rows),(int)(Math.random()*cols));
out.remove(frcurrentCell);
in.add(frcurrentCell);
ArrayList frneighbors= getNeighbors(frcurrentCell);
for (int count =0; count><frneighbors.size(); count++){
Point temp = (Point)frneighbors.get(count);
out.remove(temp);
frontier.add(temp);
}
while(frontier.size()>0){
Point temp = (Point)frontier.toArray()[((int)(Math.random()*frontier.size()))];
frontier.remove(temp);
in.add(temp);
ArrayList neighbors= getNeighbors(temp);
ArrayList choices =new ArrayList();
Point neighbor =null;
for (int count =0; count<neighbors.size(); count++){
neighbor = (Point)neighbors.get(count);
if (out.remove(neighbor)){
frontier.add(neighbor);
}
if (in.contains(neighbor)){
choices.add(neighbor);
}
}
neighbor = (Point)choices.get((int)(choices.size()*Math.random()));
Cell currentCella = maze[(int)(temp.getX())][(int)(temp.getY())];
Cell neighbora = maze[(int)(neighbor.getX())][(int)(neighbor.getY())];
if(neighbor.getX()>temp.getX()){
currentCella.S =false;
neighbora.N =false;
}
elseif(neighbor.getX()<temp.getX()){
currentCella.N =false;
neighbora.S =false;
}
elseif (neighbor.getY()>temp.getY()){
currentCella.E =false;
neighbora.W =false;
}
else{
currentCella.W=false;
neighbora.E=false;
}
}
maze[0][0].N=false;
maze[maze.length-1][maze[0].length-1].S=false;
}
private ArrayList getNeighbors(Point currentCell){
int row = (int)currentCell.getX();
int col = (int)currentCell.getY();
ArrayList answer =new ArrayList();
if (isLegalPrims(row+1,col)){
answer.add(new Point(row+1,col));
}
if (isLegalPrims(row-1,col)){
answer.add(new Point(row-1,col));
}
if (isLegalPrims(row,col+1)){
answer.add(new Point(row,col+1));
}
if (isLegalPrims(row,col-1)){
answer.add(new Point(row,col-1));
}
return answer;
}
privateboolean isLegalPrims(int row,int col){
if ((row<0)||(col<0)||(row>=maze.length)||(col>=maze[0].length)){
returnfalse;
}
returntrue;
}
publicstaticvoid main(String args[]){
PrimsFirstTry prims =new PrimsFirstTry(5,5);
prims.quickPrint();
//System.out.println(dfs); //Slow print
}
}
The super class' constructor just makes a row x col matrix of cells.
class Cell{
boolean N;
boolean S;
boolean E;
boolean W;
boolean visited;
Cell(){
N=true;
S=true;
E=true;
W=true;
visited =false;
}
publicboolean intact(){
return N&&S&&E&&W;
}
}
Now, here's what I have for Kruskal's. Any pseudocode/ explainations dealing with mazes instead of graph theory would be much appreciated.
import java.util.*;
import java.awt.*;
class KruskalsFirstTryextends Generator{
int[] ID =newint[rows*cols];
KruskalsFirstTry(){
super();
GenerateK();
}
KruskalsFirstTry(int row,int col){
super(row,col);
GenerateK();
}
privatevoid union (Cell value1, Cell value2)
if (ID[value1] == ID[value2]){
return;
}
int id2 = ID[value2];
for (int i=0 i<numValues; i++){
if (ID[i]==id2){
ID[i] = ID[value1];
}
}
}
privatevoid find(Cell value){
return ID[value]
}
privatevoid GenerateK(){
for (int count=0; count >< ID.length; count++){
ID[count] = count;
}
}
publicstaticvoid main(String args[]){
KruskalsFirstTry kr =new KruskalsFirstTry(5,5);
kr.quickPrint();
//System.out.println(dfs); //Slow print
}
}
