Bug inside Prim's MST algorithm in Java using Adjacency Matrix

42 Views Asked by At

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)

0

There are 0 best solutions below