Monday, June 1, 2015

Prims Algorithm Java Implementation (Using java.util.PriorityQueue)

Use Prims algorithm for - less nodes, large number of edges
Use Kruskal's algorithm for - more nodes, less edges (http://www.codebytes.in/2015/03/kruskals-algorithm-implementation-in.html)

Source:

import java.util.*;

public class PRIMS { 

    static class EDGE{
        int from, to;
        double weight;
        
        EDGE(int f, int t, double w){
            from = f;
            to = t;
            weight = w;
        }
    }
    
    public static ArrayList<EDGE> prims(ArrayList<ArrayList<EDGE>> G){
        if(G.isEmpty())throw new NullPointerException("The Graph is empty");
        
        ArrayList<EDGE> mst = new ArrayList<>();
        PriorityQueue<EDGE> pq = new PriorityQueue<>((Object o1, Object o2) -> {
            EDGE first = (EDGE)o1;
            EDGE second = (EDGE)o2;
            
            if(first.weight<second.weight)return -1;
            else if(first.weight>second.weight)return 1;
            else return 0;
        });
        
        for(EDGE e:G.get(0)){
            pq.add(e);
        } 
        
        boolean[] marked = new boolean[G.size()];
        marked[0] = true;
        while(!pq.isEmpty()){
            EDGE e = pq.peek();
            
            pq.poll();
            if(marked[e.from] && marked[e.to])continue;
            marked[e.from] = true;  
            for(EDGE edge:G.get(e.to)){
                if(!marked[edge.to]){
                    pq.add(edge);  
                }
            }
            marked[e.to] = true; 
            mst.add(e);
            
        }
        return mst;
    }
    
    public static ArrayList<ArrayList<EDGE>> createGraph(EDGE[] edges){
        ArrayList<ArrayList<EDGE>> G = new ArrayList<>();
        int length = edges.length*2;
        for(int i=0;i<length;++i){
            G.add(new ArrayList<>());
        }
        
        for(EDGE e:edges){
            EDGE other = new EDGE(e.to, e.from, e.weight);
            G.get(e.from).add(e);
            G.get(e.to).add(other);
            System.out.println("Added edge ["+e.from+", "+e.to+" : "+e.weight+"] "+"["+e.to+", "+e.from+" : "+e.weight+"]");
        }
        
        return G; 
    }
    
    public static void main(String[] args){
        EDGE[] edges = new EDGE[16];
        
        edges[0] = new EDGE(0, 7, 0.16);
        edges[1] = new EDGE(2, 3, 0.17);
        edges[2] = new EDGE(1, 7, 0.19);
        edges[3] = new EDGE(0, 2, 0.26);
        
        edges[4] = new EDGE(5, 7, 0.28);
        edges[5] = new EDGE(1, 3, 0.29);
        edges[6] = new EDGE(1, 5, 0.32);
        edges[7] = new EDGE(2, 7, 0.34);
        
        edges[8] = new EDGE(4, 5, 0.35);
        edges[9] = new EDGE(1, 2, 0.36);
        edges[10] = new EDGE(4, 7, 0.37);
        edges[11] = new EDGE(0, 4, 0.38);
        
        edges[12] = new EDGE(6, 2, 0.40);
        edges[13] = new EDGE(3, 6, 0.52);
        edges[14] = new EDGE(6, 0, 0.58);
        edges[15] = new EDGE(6, 4, 0.93);
        
        ArrayList<ArrayList<EDGE>> graph = createGraph(edges);
        ArrayList<EDGE> mst = prims(graph);
        
        System.out.println("MST: ");
        for(EDGE e:mst){
            System.out.println(e.from+" - "+e.to+" : "+e.weight);
        } 
    }
}

Output:

Added edge [0, 7 : 0.16] [7, 0 : 0.16]
Added edge [2, 3 : 0.17] [3, 2 : 0.17]
Added edge [1, 7 : 0.19] [7, 1 : 0.19]
Added edge [0, 2 : 0.26] [2, 0 : 0.26]
Added edge [5, 7 : 0.28] [7, 5 : 0.28]
Added edge [1, 3 : 0.29] [3, 1 : 0.29]
Added edge [1, 5 : 0.32] [5, 1 : 0.32]
Added edge [2, 7 : 0.34] [7, 2 : 0.34]
Added edge [4, 5 : 0.35] [5, 4 : 0.35]
Added edge [1, 2 : 0.36] [2, 1 : 0.36]
Added edge [4, 7 : 0.37] [7, 4 : 0.37]
Added edge [0, 4 : 0.38] [4, 0 : 0.38]
Added edge [6, 2 : 0.4] [2, 6 : 0.4]
Added edge [3, 6 : 0.52] [6, 3 : 0.52]
Added edge [6, 0 : 0.58] [0, 6 : 0.58]
Added edge [6, 4 : 0.93] [4, 6 : 0.93]
MST: 
0 - 7 : 0.16
7 - 1 : 0.19
0 - 2 : 0.26
2 - 3 : 0.17
7 - 5 : 0.28
5 - 4 : 0.35
2 - 6 : 0.4

No comments:

Post a Comment