How do i implement Prim’s algorithm in Java.

Question

I was trying to use Prim's algorithm in Java but I am unable to do that. Can anybody help me to do that?

Thanks

Answer 1

Prim’s algorithm is an algorithm which takes weighted, undirected, connected graph as an input and returns MST of a graph as an output. 

This works in a greedy manner which means it selects an arbitrary vertex and then selects the nearest vertex until there is no disconnected vertex left vertex. 

Prims Algorithms Implementation In Java - Minimum Cost Spanning Tree

public class PrimS { 

    int weightArray[][] = new int[20][20]; 

    int visited[] = new int [20]; 

    int d[] = new int[20]; 

    int p[] = new int[20]; 

    int verticeCount, edgeCount; 

    int nodeA, nodeB, weight; 

    int current, total, mincost; 

    public static void main(String args[]) throws IOException { 

        // Instantiate the graph based on input 

        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in)); 

        System.out.print("\nEnter number of vertices: "); 

        verticeCount = Integer.parseInt(buf.readLine()); 

        System.out.print("\nEnter number of edges: "); 

        edgeCount = Integer.parseInt(buf.readLine()); 

        for (int i = 1; i <= verticeCount; i++) { 

            for(int j = 1; j <= verticeCount; j++) { 

                weightArray[i][j] = 0; 

            } 

        } 

       for (int i = 1; i <= verticeCount; i++) { 

           p[i] = visited[i] = 0; 

           d[i] = 32767; 

        } 

        for (int i = 1; i <= edgeCount; i++) { 

            System.out.print("\nEnter edge nodeA, nodeB and weightArray weight: "); 

            nodeA=Integer.parseInt(in.readLine()); 

            nodeB=Integer.parseInt(in.readLine()); 

            weight=Integer.parseInt(in.readLine()); 

            weightArray[nodeA][nodeB] = weightArray[nodeB][nodeA] = weight;