> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/mst.md).

# 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 ](https://www.geeksforgeeks.org/applications-of-minimum-spanning-tree/)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.

```java
import java.util.*;

public class Solution {

    // Represents one undirected weighted edge between u and v
    static class Edge {
        int u;
        int v;
        int weight;

        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.weight = w;
        }
    }

    // ---------------------------- DSU (Union-Find) ------------------------------

    /**
     * Find the representative (root) of node x.
     * Uses path compression to flatten the tree for future queries.
     */
    public static int find(int x, int[] parent) {
        if (parent[x] != x) {
            parent[x] = find(parent[x], parent); // path compression
        }
        return parent[x];
    }

    /**
     * Union two sets using union by rank.
     * Returns true if union occurred, false if they were already connected.
     */
    public static boolean union(int x, int y, int[] parent, int[] rank) {
        int rootX = find(x, parent);
        int rootY = find(y, parent);

        if (rootX == rootY) return false; // already in same component → cycle

        // Attach smaller rank tree under larger
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }

        return true;
    }

    // ---------------------------- KRUSKAL LOGIC ------------------------------

    /**
     * Run Kruskal's MST algorithm.
     * Assumes edges are sorted by weight in ascending order.
     *
     * @param edges sorted list of edges
     * @param parent DSU parent array
     * @param rank DSU rank array
     * @param V number of vertices
     * @param E number of edges
     * @return array of V-1 edges forming the MST
     */
    public static Edge[] kruskal(Edge[] edges, int[] parent, int[] rank, int V, int E) {
        Edge[] mst = new Edge[V - 1];
        int count = 0;

        for (int i = 0; i < E && count < V - 1; i++) {
            Edge current = edges[i];

            // If union is successful, edge is safe to include in MST
            if (union(current.u, current.v, parent, rank)) {
                mst[count++] = current;
            }
        }

        return mst;
    }

    // ---------------------------- MAIN METHOD ------------------------------

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int V = sc.nextInt();   // number of vertices
        int E = sc.nextInt();   // number of edges

        Edge[] edges = new Edge[E];

        // DSU arrays (0-indexed or 1-indexed both OK, we follow 0-index)
        int[] parent = new int[V];
        int[] rank = new int[V];

        // Initialize DSU: each node is its own parent, rank = 0
        for (int i = 0; i < V; i++) {
            parent[i] = i;
            rank[i] = 0;
        }

        // Read edges
        for (int i = 0; i < E; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();

            edges[i] = new Edge(u, v, w);
        }

        // Sort edges by ascending weight
        Arrays.sort(edges, (a, b) -> a.weight - b.weight);

        // Run Kruskal
        Edge[] mst = kruskal(edges, parent, rank, V, E);

        // Print MST edges
        for (Edge e : mst) {
            int u = e.u;
            int v = e.v;
            int w = e.weight;

            // print smaller vertex first (your original formatting)
            if (u < v)
                System.out.println(u + " " + v + " " + w);
            else
                System.out.println(v + " " + u + " " + w);
        }

        sc.close();
    }
}

```