Prim's Minimum Spanning Tree Algorithm

Spanning tree of a graph is a subgraph that contains all the vertices and is also a tree. 
A minimum spanning tree of an undirected graph G is a tree formed from graph edges that connected all the vertices of G with minimum total cost (weights). A minimum spanning tree exists only if the graph is connected.
In this post, O(ELogV) algorithm for adjacency list representation is discussed.

Prim's Algorithm: 

STEP 1: Create an array parent[] of size V and initialize with -1.

STEP 2: Create a min heap (or Priority queue) of size V. Let the min heap be h.

STEP 3: Insert all vertices into h such that the key value of starting vertex is 0 and the key value of other vertices is infinite.

STEP 4: While h is not empty.

     a) u = extractMin() from h.

     b) for every adjacent v of u.

           if v is in h.

              i) update key value of v in h, if weight of an edge u-v is smaller from current key value of v.

              ii) parent[v] = u.

Source code in Java:

import java.util.LinkedList;
import java.util.Iterator;

/**
 *
 * @author Rohan
 */
public class Graph
{
    public class Heap
    {
        int[] key;
        int[] vertex;
        int[] parent;
        int capacity;
        int count;

        public Heap(int size)
        {
            this.capacity = size;
            this.key = new int[size];
            this.vertex = new int[size];
            this.parent = new int[size];
            this.count = 0;
        }
        
        public void insert()
        {
            int n = this.capacity;

            for(int j=0;j<n;j++)
            {
                this.vertex[j] = j;
            }

            for(int i=0;i<n;i++)
            {
                this.key[i] = Integer.MAX_VALUE;
                this.count++;
            }
        }
        
        public int extractMin()
        {
            int v = -1;
            if(this.count !=1)
            {
                int minValue = this.key[vertex[0]];
                v = vertex[0];
                for(int i=0;i<this.capacity;i++)
                {
                    if(check(i))
                    {
                        if(this.key[i] < minValue)
                        {
                            minValue = this.key[i];
                            v = i;
                        }
                    }
                }
                this.count--;
            
                for(int l=0;l<=this.count;l++)
                {
                    if(this.vertex[l] == v)
                    {
                        if(l!=count)
                        {
                           for(int k=l;k<this.count;k++)
                           {
                               this.vertex[k] = this.vertex[k+1];
                           }
                        }
                       
                        break;
                    }
                    
                }
            }
            return v;    
        }
        
        public boolean check(int s)
        {
            boolean f = false;
            for(int i=0;i<count;i++)
            {
                if(vertex[i] == s)
                {
                    return true;
                }       
            }
            return f;
        }
        
        public void show()
        {
            for(int j=0;j<this.count;j++)
            {
                System.out.print(this.key[j]+" ");
            }
        }
    }
    
    
    private int V;
    private int weight[][];
    private LinkedList<Integer> adj[];
    
    public Graph(int j)
    {
        V = j;
        adj = new LinkedList[V];
        weight = new int[V][V];
        
        for(int i=0;i<V;i++)
            adj[i] = new LinkedList<Integer>();   
    }
    
    public void addEdge(int v,int w)
    {
        this.adj[v].add(w);
        this.adj[w].add(v);
    }
    public void addWeight(int s,int d,int data)
    {
        weight[s][d] = data;
        weight[d][s] = data;
    }
    
    public void prims(Graph g, int s)
    {
        Heap h = new Heap(V);
        int u,v;
        h.insert();
        h.key[s] = 0;
        h.parent[s] = -1;
        while(h.count != 1)
        {
                u = h.extractMin();
                if(u != -1)
                {
                    Iterator<Integer> i = adj[u].listIterator();
                    while (i.hasNext())
                    {
                        v = i.next();
                        if (h.check(v))
                        {
                            if(h.key[v] > g.weight[u][v])
                            {
                                h.key[v] = g.weight[u][v];
                            }
                            h.parent[v] = u;
                        }
                    }
                }       
        }
        
        System.out.println();
        int sum=0;
        for(int i=0;i<h.capacity;i++)
        {
            sum = sum + h.key[i];
            System.out.print("Vertex "+i+" distance = "+h.key[i]+" Parent = "+h.parent[i]); 
           System.out.println();
        }
       
        System.out.println("Total cost is = "+sum);   
    }
    
    public static void main(String args[])
    {
        
        Graph g = new Graph(5);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 3);
        g.addEdge(2, 4);
        g.addEdge(3, 4);
        g.addWeight(0, 1, 10);
        g.addWeight(0, 2, 20);
        g.addWeight(1, 2, 30);
        g.addWeight(1, 3, 5);
        g.addWeight(2, 3, 15);
        g.addWeight(2, 4, 6);
        g.addWeight(3, 4, 8);
        
        
        g.prims(g,0);    
    }   
}    

Output:

Vertex 0 distance = 0 Parent = -1
Vertex 1 distance = 10 Parent = 0
Vertex 2 distance = 6 Parent = 4
Vertex 3 distance = 5 Parent = 1
Vertex 4 distance = 8 Parent = 3
Total cost is = 29