DSA 450 Notes

Problem Statement

Given a connected, undirected, weighted graph with V vertices and E edges, find the Minimum Spanning Tree (MST) using Kruskal's Algorithm. The MST connects all vertices with the minimum total edge weight.

Example:

Input: V = 4, Edges = [[0,1,10],[0,2,6],[0,3,5],[1,3,15],[2,3,4]]
Output: MST edges: [2,3,4], [0,3,5], [0,1,10], Total weight = 19

Noob-Friendly Explanation

Imagine you're a city planner connecting several towns with roads. Each road has a building cost (weight). You want to connect ALL towns using the cheapest set of roads — but you don't want any loops (cycles), because that wastes money.

Kruskal's algorithm is simple and greedy:

Sort all roads by cost (cheapest first).
Pick the cheapest road. If it connects two towns that aren't already connected, build it.
If it would create a loop, skip it.
Repeat until all towns are connected.

To check if two towns are already connected, we use Union-Find (a data structure that groups things together).

Approach 1: Brute Force (Without Efficient Union-Find)

Intuition

Sort edges by weight. For each edge, check if adding it creates a cycle by doing a DFS/BFS. If no cycle, include it in the MST.

Algorithm

Sort all edges by weight.
For each edge, use DFS to check if the two vertices are already connected.
If not connected, add the edge to MST.
Stop when we have V-1 edges.

java

import java.util.*;

public class KruskalBruteForce {
    public static List<int[]> kruskalMST(int V, int[][] edges) {
        // Sort edges by weight
        Arrays.sort(edges, (a, b) -> a[2] - b[2]);

        List<int[]> mst = new ArrayList<>();
        List<int[]> currentEdges = new ArrayList<>();
        int totalWeight = 0;

        for (int[] edge : edges) {
            if (mst.size() == V - 1) break;

            // Check if adding this edge creates a cycle using BFS
            if (!isConnected(V, currentEdges, edge[0], edge[1])) {
                mst.add(edge);
                currentEdges.add(edge);
                totalWeight += edge[2];
            }
        }

        System.out.println("Total MST weight: " + totalWeight);
        return mst;
    }

    static boolean isConnected(int V, List<int[]> edges, int src, int dest) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }

        boolean[] visited = new boolean[V];
        Queue<Integer> queue = new LinkedList<>();
        visited[src] = true;
        queue.add(src);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (node == dest) return true;
            for (int neighbor : adj.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int V = 4;
        int[][] edges = {{0,1,10},{0,2,6},{0,3,5},{1,3,15},{2,3,4}};
        List<int[]> mst = kruskalMST(V, edges);
        for (int[] e : mst) {
            System.out.println(e[0] + " - " + e[1] + " : " + e[2]);
        }
    }
}

Complexity Analysis

Time Complexity: O(E^2) — sorting is O(E log E), but cycle check using BFS is O(V + E) per edge.
Space Complexity: O(V + E) — for the adjacency list and visited array.

Approach 2: Optimal (Union-Find / Disjoint Set)

Intuition

Use Union-Find with path compression and union by rank for near O(1) cycle detection. Sort edges, then greedily add edges that connect two different components.

Algorithm

Sort all edges by weight.
Initialize Union-Find for V vertices.
For each edge (in sorted order), if the two vertices belong to different components, union them and add the edge to MST.
Stop when MST has V-1 edges.

java

import java.util.*;

public class KruskalOptimal {
    static int[] parent, rank;

    static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // path compression
        }
        return parent[x];
    }

    static boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;

        if (rank[px] < rank[py]) {
            parent[px] = py;
        } else if (rank[px] > rank[py]) {
            parent[py] = px;
        } else {
            parent[py] = px;
            rank[px]++;
        }
        return true;
    }

    public static List<int[]> kruskalMST(int V, int[][] edges) {
        Arrays.sort(edges, (a, b) -> a[2] - b[2]);

        parent = new int[V];
        rank = new int[V];
        for (int i = 0; i < V; i++) parent[i] = i;

        List<int[]> mst = new ArrayList<>();
        int totalWeight = 0;

        for (int[] edge : edges) {
            if (mst.size() == V - 1) break;

            if (union(edge[0], edge[1])) {
                mst.add(edge);
                totalWeight += edge[2];
            }
        }

        System.out.println("Total MST weight: " + totalWeight);
        return mst;
    }

    public static void main(String[] args) {
        int V = 4;
        int[][] edges = {{0,1,10},{0,2,6},{0,3,5},{1,3,15},{2,3,4}};
        List<int[]> mst = kruskalMST(V, edges);
        for (int[] e : mst) {
            System.out.println(e[0] + " - " + e[1] + " : " + e[2]);
        }
        // Output: 2-3:4, 0-3:5, 0-1:10, Total=19
    }
}

Complexity Analysis

Time Complexity: O(E log E) — dominated by sorting the edges. Union-Find operations are nearly O(1).
Space Complexity: O(V + E) — for parent, rank arrays and edge list.

Implement Kruskals Algorithm

Problem Statement

Noob-Friendly Explanation

Approach 1: Brute Force (Without Efficient Union-Find)

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimal (Union-Find / Disjoint Set)

Intuition

Algorithm

Complexity Analysis