Greedy

Minimum Spanning Tree (MST) Prime Kruskal algorithm

Pinterest LinkedIn Tumblr

Prime Algorithm helps to find minimum-spanning-tree. Prims algorithm is useful when a graph with lots of edges. It is significantly faster in the limit when dense graph with many more edges than vertices. Kruskal performs better in sparse graphs and it uses simpler data structures.

Write program to implement prim’s algorithm

source Code

package com.dsacode.Algorithm.greedy;
 
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
 
class AdjListNode {
    int dest;
    int weight;
    AdjListNode next;
 
    AdjListNode(int dest, int weight) {
        this.dest = dest;
        this.weight = weight;
        this.next = null;
    }
 
    public String toString() {
        return "" + dest + " - " + weight;
    }
}
 
public class Prime {
 
    int numVertices;
    public static final int INF = Integer.MAX_VALUE;
    Map < Integer, LinkedList < AdjListNode > > adjList;
    TreeMap < Integer, Integer > heap = new TreeMap < Integer, Integer >();
 
    public Prime(int numVertices) {
        this.numVertices = numVertices;
        this.adjList = new TreeMap < Integer, LinkedList < AdjListNode > >();
    }
 
    private void addEdge(Prime graph, int src, int dest, int weight) {
        AdjListNode node = new AdjListNode(dest, weight);
        LinkedList < AdjListNode > list = null;
 
        list = adjList.get(src);
        if (list == null)
            list = new LinkedList < AdjListNode >();
 
        list.addFirst(node);
        adjList.put(src, list);
 
        node = new AdjListNode(src, weight);
        list = null;
        list = adjList.get(dest);
        if (list == null)
            list = new LinkedList < AdjListNode > ();
 
        list.addFirst(node);
 
        adjList.put(dest, list);
    }
 
    public void PrimeMST(Prime graph) {
        Map < Integer, Integer > MSTholder = new TreeMap < Integer, Integer >();
        Set < Integer > set = adjList.keySet();
        for (Integer i : set) {
            createHeap(i, INF);
        }
 
        while (heap.size() != 0) {
            int minEdgeVertex = findMin();
            heap.remove(minEdgeVertex);
 
            LinkedList < AdjListNode > list = adjList.get(minEdgeVertex);
            Iterator < AdjListNode > it = list.iterator();
 
            while (it.hasNext()) {
                AdjListNode node = it.next();
                int vertex = node.dest;
 
                if ((heap.containsKey(vertex)) && (node.weight < INF)) {
                    heap.put(vertex, node.weight);
                    MSTholder.put(vertex, minEdgeVertex);
                }
            }
        }
 
         
         printMST(MSTholder);
        long cost = MSTCost(MSTholder);
        System.out.println("Minimum spanning tree Cost is :" + cost);
 
    }
 
     
    private long MSTCost(Map < Integer, Integer > MSTholder) {
        Set< Map.Entry < Integer, Integer > > set = MSTholder.entrySet();
 
        long sum = 0;
        for (Map.Entry < Integer, Integer> entry : set) {
 
            int key = entry.getKey();
            int value = entry.getValue();
 
            List < AdjListNode > list = adjList.get(value);
            if (list != null) {
                for (int j = 0; j < list.size(); j++) {
                    AdjListNode node = list.get(j);
                    if ((node.dest) == key) {
                        sum += node.weight;
                    }
                }
            }
        }
        return sum;
    }
 
     
    private void printMST(Map < Integer, Integer > MSTholder) {
 
        System.out.println("Minimum Spanning Tree is : ");
        Set < Map.Entry < Integer, Integer > > set = MSTholder.entrySet();
 
        for (Map.Entry < Integer, Integer > entry : set) {
            System.out.println(entry.getKey() + " -- " + entry.getValue());
        }
    }
 
     
    public void createHeap(int vertex, Integer weight) {
        if (heap == null)
            heap = new TreeMap < Integer, Integer >();
 
        heap.put(vertex, weight);
    }
 
     
    private int findMin() {
        Set < Map.Entry < Integer, Integer > > list = heap.entrySet();
 
        int minKey = heap.firstKey();
        int minValue = INF;
        if (list != null) {
            for (Map.Entry < Integer, Integer > entry : list) {
                if (minValue > entry.getValue()) {
                    minValue = entry.getValue();
                    minKey = entry.getKey();
                }
            }
        }
        return minKey;
    }
 
     
    public static void main(String[] args) throws Exception {
        int numvertices = 9;
 
        Prime graph = new Prime(numvertices);
        graph.addEdge(graph, 0, 1, 4);
        graph.addEdge(graph, 0, 7, 8);
        graph.addEdge(graph, 1, 2, 8);
        graph.addEdge(graph, 1, 7, 11);
        graph.addEdge(graph, 2, 3, 7);
        graph.addEdge(graph, 2, 8, 2);
        graph.addEdge(graph, 2, 5, 4);
        graph.addEdge(graph, 3, 4, 9);
        graph.addEdge(graph, 3, 5, 14);
        graph.addEdge(graph, 4, 5, 10);
        graph.addEdge(graph, 5, 6, 2);
        graph.addEdge(graph, 6, 7, 1);
        graph.addEdge(graph, 6, 8, 6);
        graph.addEdge(graph, 7, 8, 7);
 
        graph.PrimeMST(graph);
         
    }
 
     
}

Output

Minimum Spanning Tree is:
1 -- 0
2 -- 1
3 -- 4
4 -- 5
5 -- 2
6 -- 5
7 -- 6
8 -- 2
Minimum spanning tree Cost is: 40

Algorithm Explanation

Create a Min Heap of size V where V is the number of vertices in the given graph.
Every node of min heap contains vertex number and key value of the vertex.
Initialize Min Heap with first vertex as root. The key value assigned to all other vertices is infinite.
If Min Heap is not empty, extract the min value node from Min Heap.
Every adjacent vertex v of u, check if v is in Min Heap.

Time Complexity

Best CaseAverage CaseWorst Case
O(E + V log V)

Reference

  1. https://en.wikipedia.org/?title=Prim%27s_algorithm
  2. http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/11-Graph/prim2.html

Write A Comment