Building the Backbone

[!NOTE] This module explores the core principles of Minimum Spanning Tree (MST), deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

Problem: Given a weighted, connected, undirected graph, select a subset of edges that:

1. Connects all vertices.
2. Has no cycles (it’s a tree).
3. Has the minimum total weight.

Algorithms:

1. Kruskal’s: Greedy. Sort edges by weight. Add edge if it doesn’t form a cycle (Use Union-Find).
2. Prim’s: Greedy. Start at arbitrary node. Always pick the smallest edge connecting Visited to Unvisited (Use Min-Heap).

---

2. Interactive Analysis: Kruskal’s Algorithm

Sort edges: (0-1, 1), (1-2, 2), (2-3, 3), (0-3, 5). Iterate:

1. 0-1: Cost 1. Union(0, 1).
2. 1-2: Cost 2. Union(1, 2).
3. 2-3: Cost 3. Union(2, 3).
4. 0-3: Cost 5. 0 and 3 already connected. Skip (Cycle).

Ready. Edges sorted.

Total Cost: 0

---

3. Implementation

Kruskal’s (Edges + Union Find)

Java

Go

// Uses DSU class from Union-Find module
public int minCostConnectPoints(int[][] points) {
    int n = points.length;
    List<int[]> edges = new ArrayList<>();

    // Generate all edges
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int dist = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
            edges.add(new int[]{i, j, dist});
        }
    }

    // Sort by weight
    Collections.sort(edges, (a, b) -> a[2] - b[2]);

    DSU dsu = new DSU(n);
    int cost = 0;
    int edgesCount = 0;

    for (int[] edge : edges) {
        if (dsu.union(edge[0], edge[1])) {
            cost += edge[2];
            edgesCount++;
            if (edgesCount == n - 1) break;
        }
    }

    return cost;
}

// Uses DSU struct
func minCostConnectPoints(points [][]int) int {
    n := len(points)
    edges := [][]int{}

    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            dist := abs(points[i][0]-points[j][0]) + abs(points[i][1]-points[j][1])
            edges = append(edges, []int{i, j, dist})
        }
    }

    sort.Slice(edges, func(i, j int) bool {
        return edges[i][2] < edges[j][2]
    })

    dsu := NewDSU(n)
    cost := 0
    count := 0

    for _, e := range edges {
        if dsu.Union(e[0], e[1]) {
            cost += e[2]
            count++
            if count == n-1 { break }
        }
    }
    return cost
}

func abs(x int) int { if x < 0 { return -x }; return x }

---

4. Complexity Analysis

Strategy	Time	Space	Notes
Kruskal’s	O(E log E)	O(V + E)	Best for Sparse Graphs.
Prim’s	O(E log V)	O(V + E)	Best for Dense Graphs.