1

I'm trying implement Prim's Minimum Spanning Tree Algorithm of a graph represented using Adjacency Matrix in Java. The code is running successfully, but not able to generate expected output. The Algorithm only selects the first vertex and doesn't move forward. What am I doing wrong? Here is my implementation of the Algorithm.

import java.util.Arrays;

public class WeightedUndirectedGraph {
    private final int V;
    private final int[][] adjMatrix;

    public WeightedUndirectedGraph(int V){
        this.V = V;
        adjMatrix = new int[V][V];
    }

    public int getV() {
        return V;
    }

    public int[][] getAdjMatrix() {
        return adjMatrix;
    }

    public void addEdge(int u, int v, int weight) throws IndexOutOfBoundsException{
        if(u >= this.V || v >= this.V) throw new ArrayIndexOutOfBoundsException("Index out of Bounds");
        else {
            adjMatrix[u][v] = weight;
            adjMatrix[v][u] = weight;
        }
    }

    public void removeEdge(int u, int v) throws IndexOutOfBoundsException{
        if(u >= this.V || v >= this.V) throw new ArrayIndexOutOfBoundsException("Index out of Bounds");
        else {
            adjMatrix[u][v] = 0;
            adjMatrix[v][u] = 0;
        }
    }

    /**
     * Prim's Greedy Algorithm to find Minimum Spanning Tree
     */
    public void primsMST(){
        int minimum = Integer.MAX_VALUE;
        int MST_weight = 0;
        boolean[] selected = new boolean[this.V];
        Arrays.fill(selected, false);
        int no_of_edges = 0;
        int x = 0;
        int y = 0;
        int max_edges = V - 1;
        selected[0] = true;
        System.out.println("Selected Edges in a Minimum Spanning Tree are:");
        while(no_of_edges < max_edges){
            for(int i = 0; i < V; i++){
                if(selected[i]){
                    for(int j = 0; j < V; j++){
                        if(!selected[j] && adjMatrix[i][j] != 0){
                            if(adjMatrix[i][j] < minimum){
                                minimum = adjMatrix[i][j];
                                MST_weight += adjMatrix[i][j];
                                x = i;
                                y = j;
                            }
                        }
                    }
                }
            }
            System.out.println(x + "-" + y + " : " + adjMatrix[x][y]);
            selected[y] = true;
            no_of_edges++;
        }
        System.out.println("Total weight of the Minimum Spanning Tree is " + MST_weight);
    }
}

Here is my main function call:

WeightedUndirectedGraph WUG = new WeightedUndirectedGraph(5);
WUG.addEdge(0, 1, 1);
WUG.addEdge(0, 2, 2);
WUG.addEdge(0, 3, 7);
WUG.addEdge(1, 3, 5);
WUG.addEdge(1, 2, 3);
WUG.addEdge(2, 3, 4);
WUG.primsMST();

I tried running the code, this is my output:

Selected Edges in a Minimum Spanning Tree are:
0-1 : 1
0-1 : 1
0-1 : 1
0-1 : 1
Total weight of the Minimum Spanning Tree is 1

I'm getting 0-1 repeatedly (i.e not progressing from start vertex)

2
  • Can you, please, edit the question to include something about your attempts to debug this? Commented Nov 20, 2023 at 17:07
  • @OldDogProgrammer, I'm assuming bug inside for loop where the next vertex is selected. Commented Nov 21, 2023 at 4:37

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.