Hello,
I just started learning Java, and I'm having problems getting Kruskal's algorithm to work properly. While I have had more success implimenting this in C++, I'm still having issues there. I have a feeling my find() method may be the cause. I've been scouring the net trying to find a solution, but to no avail.
Some issues:
program incorrectly allows a cycle
allowing cycle produces incorrect weight of the tree
issues when arrangeEdges() is called (works when called from initializer() but not from spanningTree()
I've been stuck on this for a week now, and finally decided I couldn't solve this on my own. Any and all help would be appreciated.
Thanks in advance.
public class Kruskal
{
private static int ARRAY_SIZE = 1000;
private static int MAX = 999;
public EdgeInfo edge[] = new EdgeInfo[ARRAY_SIZE];
public int tree[][] = new int[ARRAY_SIZE][3];
public int set[] = new int[ARRAY_SIZE];
public int n; // Global num of vertices
public int numEdges = 0;
int sum = 0;
// Constructor
public Kruskal() {
buildArray();
}
private void buildArray() {
for(int i = 0; i < ARRAY_SIZE; i++){
edge[i] = new EdgeInfo();
}
}
public int readEdges(int vertices, int M[][])
{
int numPaths = 1;
int cost = 0;
Scanner in = new Scanner(System.in);
//n = vertices;
//System.out.println(n);
System.out.print("\nEnter the weight between the edges [i][j] below (use 999 for no weight).\n");
for (int i = 1; i <= n; i++)
for (int j = 1; j < i; j++)
{
System.out.print("Enter weight of [" + i + "][" + j + "]: ");
cost = in.nextInt();
if (cost != MAX)
{
edge[numPaths].u = i;
edge[numPaths].v = j;
edge[numPaths].weight = cost;
numPaths++;
}
}
return (numPaths - 1);
}
public void makeSet(int vert)
{
int k = vert;
for (int i = 1; i <= k; i++)
set[i] = i;
}
public int find(int vertex)
{
int j = vertex;
while(set[j] != j)
j = set[j];
return (j);
}
public void joinSet(int v1, int v2)
{
if (v1 < v2)
set[v2] = v1;
else
set[v1] = v2;
}
public void arrangeEdges(int ecount)
{
int k = ecount;
EdgeInfo temp = new EdgeInfo();
for (int i = 1; i < k; i++)
for (int j = 1; j <= k - i; j++)
if (edge[j].weight > edge[j + 1].weight)
{
temp = edge[j];
edge[j] = edge[j + 1];
edge[j + 1] = temp;
}
}
public int spanningTree(int ecount)
{
int t, sum, k, counter = 1;
k = ecount;
t = 1;
sum = 0;
arrangeEdges(k); //ISSUE
// Display the sorted array
for (int j = 1; j <= k; j++)
{
System.out.print("[" + edge[j].u);
System.out.print("][" + edge[j].v);
System.out.println("]=" + edge[j].weight);
}
for (int i = 1; i <= k; i++)
{
if (find(edge[i].u) != find(edge[i].v))
{
tree[t][1] = edge[i].u;
tree[t][2] = edge[i].v;
if(counter < n)
{
sum += edge[i].weight;
counter++;
}
joinSet(edge[t].u, edge[t].v);
t++;
}
}
return sum;
}
public void display(int cost)
{
int i;
System.out.println("\nThe Edges of the Minimum Spanning Tree are:");
for (i = 1; i < n; i++)
System.out.print(tree[i][1] + " - " + tree[i][2] + "\n");
System.out.print("\nThe cost of the tree is: " + cost);
}
int initializar(int vertices, int M[][])
{
int ecount = 0;
int totalcost = 0;
Kruskal k = new Kruskal();
ecount = readEdges(vertices, M);
numEdges = ecount;
System.out.println("num edges: " + numEdges);
k.makeSet(vertices);
totalcost = k.spanningTree(ecount); // ISSUE
k.display(sum);
return 0;
}
}
public class EdgeInfo
{
// Struct
public int u;
public int v;
public int weight;
public EdgeInfo()
{
// Initializes set
u = 0;
v = 0;
weight = 0;
}
}
public class KruskalTester {
public static void main(String args[])
{
int[][] M = new int[1000][1000];
int numVert;
Kruskal k = new Kruskal();
System.out.print("\nEnter the number of vertices: ");
Scanner in = new Scanner(System.in);
numVert = in.nextInt();
k.n = numVert;
k.initializar(numVert, M);
}
}