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);
    }
}

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'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.

What are your thoughts?

This article has been dead for over six months. Start a new discussion instead.