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.

``````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();

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);
}
}``````
2
Contributors
4
Replies
7
Views
8 Years
Discussion Span
Last Post by Pezzy

I implemented tihs algorithm before. My approach was different.
anyway, just wonder why readEdges method has a parameter M[][]?

Agreed, I don't need M[][] at all... unless I decide to put my adjacency matrix in it. But that shouldn't be needed.

I suggest you to change your approach. If you agree, I can tell you a more elegant way.

I'm more than willing to change my approach. The only problem is that I need to get this completed in about 48 hours.

One of my earlier attempts at doing this in C++ utilized vectors. For this project, I'll lose points if I don't use a Heap (which I wasn't going to do) and if I don't give the program the ability to read in the paths/weights from a file, but I can pretty easily impliment that.