Prim's minimum spanning tree algorithm: lazy implementation


import java.util.Queue;
import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.HashSet;
import java.util.List;
import java.util.ArrayList;

class PrimMinimumSpanningTreeLazy {
    private boolean[] visited; // MST vertices
    private Queue mst; // MST edges
    private Queue pq; // PriorityQueue of edges 
    private double weight;
    
    public PrimMinimumSpanningTreeLazy(EdgeWeightedGraph G) {
        this.visited = new boolean[G.V()];
        this.mst = new ArrayDeque<>();
        this.pq = new PriorityQueue<>();
        
        // assume G is connected
        visit(G, 0);
        
        while (!pq.isEmpty() && mst.size() < G.V()-1) {
            // repeatedly delete the min weight edge e = v–w from PQ
            Edge edge = pq.poll();
            // greedily add edges to MST
            int v = edge.either(), w = edge.other(v);
            
            // ignore if both endpoints in T
            if(visited[v] && visited[w]) {
                continue;
            }
            
            // add edge e to tree
            mst.add(edge);
            this.weight += edge.weight();
            
            // add v or w to tree
            if(!visited[v]) {
                visit(G, v);
            }
            if(!visited[w]) {
                visit(G, w);
            }
        }
    }
    
    public Iterable edges() { 
        return mst;
    }
    
    public double weight() { 
        return weight;
    }
    
    private void visit(EdgeWeightedGraph G, int v) {
        visited[v] = true; // add v to T
        // for each edge e = v–w, add to PQ if w not already in T
        for(Edge edge : G.adj(v)) {
            if(!visited[edge.either()] || !visited[edge.other(edge.either())]) {
                pq.add(edge);
            }
        }
    }
    
    static class EdgeWeightedGraph {
        private final int V;
        private final List[] adj;
        
        /** create an empty graph with V vertices */
        public EdgeWeightedGraph(int V) {
            this.V = V;
            adj = new ArrayList[V]; // // create empty graph with V vertices
            for (int v = 0; v < V; v++) {
                adj[v] = new ArrayList<>();
            }
        }
        
        /** add weighted edge e to this graph */
        public void addEdge(Edge e) {
            int v = e.either(), w = e.other(v);
            adj[v].add(e);
            adj[w].add(e);
        }
        
        /** Edges adjcent to v */
        public Iterable adj(int v) { 
            return adj[v]; 
        }
        
        /** all edges in this graph */
        Iterable edges() {
            Set allEdges = new HashSet<>();
            for(List list : adj) {
                allEdges.addAll(list);
            }
            return allEdges;
        }
        
        /** number of vertices */
        public int V()  {
            return V;
        }
        
        /** number of edges */
        int E()  {
            int edges = 0;
            for(List edge : adj) {
                edges += edge.size();
            }
            return edges/2; // Since each edge counted twice
        }
    }
    
    static class Edge implements Comparable {
        private final int v;
        private final int w;
        private final double weight;
        
        /** create a weighted edge v-w */
        Edge(int v, int w, double weight) {
            this.v = v;
            this.w = w;
            this.weight = weight;
        }
        
        /** either endpoint */
        int either() {
            return v;
        }
        
        /** the endpoint that's not v */
        int other(int v) {
            if(this.v == v) {
                return w;
            }
            return v;
        }
        
        /** compare this edge to that edge */
        public int compareTo(Edge that) {
            if(this.weight < that.weight) {
                return -1;
            } else if(this.weight > that.weight) {
                return 1;
            }
            return 0;
        }
        
        /** the weight */
        double weight() {
            return weight;
        }
        
        /** string representation */
        public String toString() {
            return "Edge: " + v + "-" + w + ", Weight: " + weight;
        }
    }
    
    private static EdgeWeightedGraph dummyGraph() {
        String[][] input = {
            {"0", "7", "0.16"},
            {"2", "3", "0.17"},
            {"1", "7", "0.19"},
            {"0", "2", "0.26"},
            {"5", "7", "0.28"},
            {"1", "3", "0.29"},
            {"1", "5", "0.32"},
            {"2", "7", "0.34"},
            {"4", "5", "0.35"},
            {"1", "2", "0.36"},
            {"4", "7", "0.37"},
            {"0", "4", "0.38"},
            {"6", "2", "0.40"},
            {"3", "6", "0.52"},
            {"6", "0", "0.58"},
            {"6", "4", "0.93"}
        };
        EdgeWeightedGraph G = new EdgeWeightedGraph(8);
        for(int i = 0; i < input.length; i++) {
            int v = Integer.parseInt(input[i][0]);
            int w = Integer.parseInt(input[i][1]);
            double weight = Double.parseDouble(input[i][2]);
            Edge edge = new Edge(v, w, weight);
            G.addEdge(edge);
        }
        return G;
    }
    
	public static void main (String[] args) {
		PrimMinimumSpanningTreeLazy primMinimumSpanningTreeLazy = 
		    new PrimMinimumSpanningTreeLazy(dummyGraph());
		    System.out.println("PrimMinimumSpanningTreeLazy: Weight = " 
		    + primMinimumSpanningTreeLazy.weight());
		System.out.println("MST edges: ");
		primMinimumSpanningTreeLazy.edges()
		    .forEach(edge -> 
		        System.out.print(edge.either() + "-" + edge.other(edge.either()) + ", "));
	}
}

Output
KruskalMinimumSpanningTree: Weight = 1.81
MST edges: 
0-7, 1-7, 0-2, 2-3, 5-7, 4-5, 6-2, 

Comments

Popular posts from this blog

SQL basic interview question

gsutil Vs Storage Transfer Service Vs Transfer Appliance