MST_example.java

/**
 *
 * @author pulkit4tech
 */

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;

public class MST_example implements Runnable {

    BufferedReader c;
    PrintWriter pout;
    // static long mod = 1000000007;

    public void run() {
        try {
            c = new BufferedReader(new InputStreamReader(System.in));
            pout = new PrintWriter(System.out, true);
            solve();
            pout.close();
        } catch (Exception e) {
            pout.close();
            e.printStackTrace();
            System.exit(1);
        }
    }

    public static void main(String[] args) throws Exception {
        new Thread(new MST_example()).start();
    }

    void solve() throws Exception {
      //  kruskal_mst();
        prim_mst();
    }

    void prim_mst(){
    	int graph[][] = new int[][] {{0, 2, 0, 6, 0},
            {2, 0, 3, 8, 5},
            {0, 3, 0, 0, 7},
            {6, 8, 0, 0, 9},
            {0, 5, 7, 9, 0},
           };
        primMSThelper(graph);
    }

    int minKey(int key[],boolean mstSet[]){
    	int min = Integer.MAX_VALUE,min_i = -1;

    	for(int v=0;v<key.length;v++){
    		if(mstSet[v]==false&&key[v]<min){
    			min = key[v];
    			min_i = v;
    		}
    	}
    	return min_i;
    }

    void printMST(int parent[],int graph[][]){
    	pout.println("Edge   weight");
    	for(int i=1;i<parent.length;i++){
    		pout.println(parent[i]+"-"+i+"     "+graph[i][parent[i]]);
    	}
    }

    void primMSThelper(int graph[][]){
    	//to store parent
    	int parent[] = new int[graph.length];
    	//key to pickup min vertices
    	int key[] = new int[graph.length];
    	boolean set[]= new boolean[graph.length];
    	Arrays.fill(key, Integer.MAX_VALUE);
    	Arrays.fill(set, false);
    	key[0] = 0;
    	parent[0] = -1;

    	for(int i=0;i<graph.length-1;i++){
    		int u = minKey(key, set);
    		set[u] = true;

    		for(int v=0;v<graph.length;v++){
    			if(graph[u][v]!=0&&!set[v]&&graph[u][v]<key[v]){
    				parent[v] = u;
    				key[v] = graph[u][v];
    			}
    		}
    	}

    	printMST(parent, graph);
    }

    void kruskal_mst() {

        //reference geeksforgeeks
        int V = 4;
        int E = 5;
        Graph graph = new Graph(V, E);

        // add edge 0-1
        graph.edge[0].src = 0;
        graph.edge[0].dest = 1;
        graph.edge[0].weight = 10;

        // add edge 0-2
        graph.edge[1].src = 0;
        graph.edge[1].dest = 2;
        graph.edge[1].weight = 6;

        // add edge 0-3
        graph.edge[2].src = 0;
        graph.edge[2].dest = 3;
        graph.edge[2].weight = 5;

        // add edge 1-3
        graph.edge[3].src = 1;
        graph.edge[3].dest = 3;
        graph.edge[3].weight = 15;

        // add edge 2-3
        graph.edge[4].src = 2;
        graph.edge[4].dest = 3;
        graph.edge[4].weight = 4;

        graph.KruskalMST();
    }

    class Graph {

        class Edge implements Comparable<Edge> {

            int src, dest, weight;

            public int compareTo(Edge compareEdge) {
                return this.weight - compareEdge.weight;
            }
        };

        // A class to represent a subset for union-find
        class subset {

            int parent, rank;
        };

        int V, E;
        Edge edge[];


        Graph(int v, int e) {
            V = v;
            E = e;
            edge = new Edge[E];
            for (int i = 0; i < e; ++i) {
                edge[i] = new Edge();
            }
        }


        int find(subset subsets[], int i) {

            if (subsets[i].parent != i) {
                subsets[i].parent = find(subsets, subsets[i].parent);
            }

            return subsets[i].parent;
        }

        // A function that does union of two sets of x and y
        // (uses union by rank)
        void Union(subset subsets[], int x, int y) {
            int xroot = find(subsets, x);
            int yroot = find(subsets, y);

            // Attach smaller rank tree under root of high rank tree
            // (Union by Rank)
            if (subsets[xroot].rank < subsets[yroot].rank) {
                subsets[xroot].parent = yroot;
            } else if (subsets[xroot].rank > subsets[yroot].rank) {
                subsets[yroot].parent = xroot;
            } // If ranks are same, then make one as root and increment
            // its rank by one
            else {
                subsets[yroot].parent = xroot;
                subsets[xroot].rank++;
            }
        }

        // The main function to construct MST using Kruskal's algorithm
        void KruskalMST() {
            Edge result[] = new Edge[V];  // Tnis will store the resultant MST
            int e = 0;  // An index variable, used for result[]
            int i = 0;  // An index variable, used for sorted edges
            for (i = 0; i < V; ++i) {
                result[i] = new Edge();
            }

            // Step 1:  Sort all the edges in non-decreasing order of their
            // weight.  If we are not allowed to change the given graph, we
            // can create a copy of array of edges
            Arrays.sort(edge);

            // Allocate memory for creating V ssubsets
            subset subsets[] = new subset[V];
            for (i = 0; i < V; ++i) {
                subsets[i] = new subset();
            }

            // Create V subsets with single elements
            for (int v = 0; v < V; ++v) {
                subsets[v].parent = v;
                subsets[v].rank = 0;
            }

            i = 0;  // Index used to pick next edge

            // Number of edges to be taken is equal to V-1
            while (e < V - 1) {
                // Step 2: Pick the smallest edge. And increment the index
                // for next iteration
                Edge next_edge = new Edge();
                next_edge = edge[i++];

                int x = find(subsets, next_edge.src);
                int y = find(subsets, next_edge.dest);

                // If including this edge does't cause cycle, include it
                // in result and increment the index of result for next edge
                if (x != y) {
                    result[e++] = next_edge;
                    Union(subsets, x, y);
                }
                // Else discard the next_edge
            }

            // print the contents of result[] to display the built MST
            System.out.println("Following are the edges in the constructed MST");
            for (i = 0; i < e; ++i) {
                System.out.println(result[i].src + " -- " + result[i].dest + " == "
                        + result[i].weight);
            }
        }
    }

}