MST

What is Minimum Spanning Tree? Given a connected and undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees. A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected and undirected graph is a spanning tree with weight less than or equal to the weight of every other spanning tree. The weight of a spanning tree is the sum of weights given to each edge of the spanning tree.

How many edges does a minimum spanning tree has? A minimum spanning tree has (V – 1) edges where V is the number of vertices in the given graph.

What are the applications of Minimum Spanning Tree? See this for applications of MST.

Below are the steps for finding MST using Kruskal’s algorithm

1. Sort all the edges in non-decreasing order of their weight. 2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. 3. Repeat step#2 until there are (V-1) edges in the spanning tree.

public class Solution {
    static class edge {
        int v1, v2, w;

        public edge(int a, int b, int c) {
            v1 = a;
            v2 = b;
            w = c;
        }
    }

    public static int findTopParent(int v, HashMap<Integer, Integer> map) {
        int key = v;
        int value = map.get(v);
        while (value != key) {
            key = value;
            value = map.get(value);
        }
        return value;
    }

    public static edge[] kruskal(edge[] input, HashMap<Integer, Integer> map, int V, int E) {
        edge[] output = new edge[V - 1];
        for (int i = 0, count = 0; i < E && count < V - 1; i++) {
            edge current_edge = input[i];
            int top_parent_of_v1 = findTopParent(current_edge.v1, map);
            int top_parent_of_v2 = findTopParent(current_edge.v2, map);
            if (top_parent_of_v1 == top_parent_of_v2)
                continue;
            else {
                map.put(top_parent_of_v1, top_parent_of_v2); // making the required changes in the parent array
                output[count] = current_edge; // adding this edge into the output edge array
                count++;
            }
        }
        return output;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int V = s.nextInt();
        int E = s.nextInt();
        edge[] input = new edge[E];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < E; i++) {
            int ei = s.nextInt();
            int ej = s.nextInt();
            int wi = s.nextInt();
            // Using hashmap as a parent array
            map.put(ei, ei);
            map.put(ej, ej);

            edge temp = new edge(ei, ej, wi);
            input[i] = temp;
        }
        Arrays.sort(input, (a, b) -> a.w - b.w);
        edge[] output = kruskal(input, map, V, E);
        for (int i = 0; i < V - 1; i++) {
            if (output[i].v1 < output[i].v2)
                System.out.print(output[i].v1 + " " + output[i].v2 + " " + output[i].w);
            else
                System.out.print(output[i].v2 + " " + output[i].v1 + " " + output[i].w);
            System.out.println();
        }
    }
}