Minimum Spanning Tree（最小生成樹，MST）

# python
# IDEA: Kruskal — sort edges, take each one that joins two different components
# time = O(E log E), space = O(V + E)
def kruskal(n, edges):
    """n nodes 0..n-1, edges = [(weight, a, b), ...]; return MST cost or -1."""
    parent = list(range(n))
    rank = [0] * n

    def find(x):
        # path halving: point x at its grandparent while walking up
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        root_a, root_b = find(a), find(b)
        if root_a == root_b:
            return False                # already connected -> this edge closes a cycle
        if rank[root_a] < rank[root_b]:
            root_a, root_b = root_b, root_a
        parent[root_b] = root_a         # hang the shorter tree under the taller one
        if rank[root_a] == rank[root_b]:
            rank[root_a] += 1
        return True

    total_cost = 0
    edges_used = 0
    for weight, a, b in sorted(edges):
        if union(a, b):
            total_cost += weight
            edges_used += 1
            if edges_used == n - 1:     # a tree on n nodes has exactly n - 1 edges
                return total_cost
    return total_cost if n <= 1 else -1  # ran out of edges: disconnected

// java
// IDEA: Kruskal — sort edges, take each one that joins two different components
// time = O(E log E), space = O(V + E)
public int kruskal(int n, int[][] edges) {    // edges[i] = {weight, a, b}
    int[] parent = new int[n];
    int[] rank = new int[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }

    int[][] sorted = edges.clone();
    Arrays.sort(sorted, (x, y) -> Integer.compare(x[0], y[0]));

    int totalCost = 0;
    int edgesUsed = 0;
    for (int[] edge : sorted) {
        int rootA = find(parent, edge[1]);
        int rootB = find(parent, edge[2]);
        if (rootA == rootB) {
            continue;                       // would close a cycle
        }
        if (rank[rootA] < rank[rootB]) {
            int tmp = rootA; rootA = rootB; rootB = tmp;
        }
        parent[rootB] = rootA;
        if (rank[rootA] == rank[rootB]) {
            rank[rootA]++;
        }
        totalCost += edge[0];
        edgesUsed++;
        if (edgesUsed == n - 1) {
            return totalCost;
        }
    }
    return n <= 1 ? 0 : -1;                 // disconnected
}

private int find(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];      // path halving
        x = parent[x];
    }
    return x;
}

graph G, 5 nodes:  0-1 (2)  1-2 (3)  2-4 (4)  1-4 (5)  0-3 (6)  1-3 (8)  3-4 (9)

    0 ---2--- 1 ---3--- 2
    |       /   \      /
    6     8       5   4
    |   /           \/
    3 -------9------ 4

sorted edge   find(a) == find(b)?   action      components after               total
0-1 (2)       no                    take        {0,1} {2} {3} {4}                2
1-2 (3)       no                    take        {0,1,2} {3} {4}                  5
2-4 (4)       no                    take        {0,1,2,4} {3}                    9
1-4 (5)       YES — 1 and 4 joined  skip        (would close cycle 1-2-4)
0-3 (6)       no                    take        {0,1,2,3,4}                     15
              4 edges = n - 1  ->  stop; 1-3 (8) and 3-4 (9) are never looked at

MST = {0-1, 1-2, 2-4, 0-3}, cost 15

# python
# IDEA: Kruskal that returns the chosen edges; maximum=True builds a MAXIMUM spanning tree
# time = O(E log E), space = O(V + E)
def kruskal_tree(n, edges, maximum=False):
    """edges = [(weight, a, b), ...]; return (total, tree_edges).
    len(tree_edges) < n - 1 means the graph is disconnected (the result is a forest)."""
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    total = 0
    tree_edges = []
    for weight, a, b in sorted(edges, reverse=maximum):
        root_a, root_b = find(a), find(b)
        if root_a == root_b:
            continue                    # closes a cycle
        parent[root_a] = root_b
        total += weight
        tree_edges.append((a, b, weight))
        if len(tree_edges) == n - 1:
            break
    return total, tree_edges

# python
# IDEA: Prim — the cheapest edge leaving the tree is always safe (cut property)
# time = O(E log V), space = O(V + E)
import heapq

def prim(n, adj):
    """adj[u] = [(weight, v), ...] for an undirected graph; return MST cost or -1."""
    in_tree = [False] * n
    min_heap = [(0, 0)]                 # (cost to join the tree, node)
    total_cost = 0
    nodes_joined = 0

    while min_heap and nodes_joined < n:
        cost, node = heapq.heappop(min_heap)
        if in_tree[node]:
            continue                    # a stale, more expensive offer for this node
        in_tree[node] = True
        total_cost += cost
        nodes_joined += 1
        for weight, neighbour in adj[node]:
            if not in_tree[neighbour]:
                heapq.heappush(min_heap, (weight, neighbour))

    return total_cost if nodes_joined == n else -1

// java
// IDEA: Prim — the cheapest edge leaving the tree is always safe (cut property)
// time = O(E log V), space = O(V + E)
public int prim(int n, List<List<int[]>> adj) {  // adj.get(u) = [{weight, v}, ...]
    boolean[] inTree = new boolean[n];
    PriorityQueue<int[]> minHeap = new PriorityQueue<>((x, y) -> Integer.compare(x[0], y[0]));
    minHeap.offer(new int[]{0, 0});              // {cost to join the tree, node}
    int totalCost = 0;
    int nodesJoined = 0;

    while (!minHeap.isEmpty() && nodesJoined < n) {
        int[] top = minHeap.poll();
        int cost = top[0];
        int node = top[1];
        if (inTree[node]) {
            continue;                            // stale offer
        }
        inTree[node] = true;
        totalCost += cost;
        nodesJoined++;
        for (int[] edge : adj.get(node)) {
            if (!inTree[edge[1]]) {
                minHeap.offer(new int[]{edge[0], edge[1]});
            }
        }
    }
    return nodesJoined == n ? totalCost : -1;
}

pop        in tree?   action                 push                         heap after              total
(0, 0)     no         join 0                 (2,1) (6,3)                  (2,1) (6,3)                 0
(2, 1)     no         join 1 via 0-1         (3,2) (5,4) (8,3)            (3,2) (5,4) (6,3) (8,3)     2
(3, 2)     no         join 2 via 1-2         (4,4)                        (4,4) (5,4) (6,3) (8,3)     5
(4, 4)     no         join 4 via 2-4         (9,3)                        (5,4) (6,3) (8,3) (9,3)     9
(5, 4)     YES        stale — skip                                        (6,3) (8,3) (9,3)
(6, 3)     no         join 3 via 0-3                                                                 15
all 5 nodes joined -> stop

MST = {0-1, 1-2, 2-4, 0-3}, cost 15   — the same tree Kruskal built, found in a different order

# python
# IDEA: Prim that records which tree node each node was joined from
# time = O(E log V), space = O(V + E)
import heapq

def prim_tree(n, adj, start=0):
    """adj[u] = [(weight, v), ...]; return (total, tree_edges), or None if disconnected."""
    in_tree = [False] * n
    min_heap = [(0, start, -1)]         # (edge weight, node, the tree node it joins from)
    total = 0
    tree_edges = []

    while min_heap:
        weight, node, came_from = heapq.heappop(min_heap)
        if in_tree[node]:
            continue
        in_tree[node] = True
        total += weight
        if came_from != -1:
            tree_edges.append((came_from, node, weight))
        for next_weight, neighbour in adj[node]:
            if not in_tree[neighbour]:
                heapq.heappush(min_heap, (next_weight, neighbour, node))

    return (total, tree_edges) if len(tree_edges) == n - 1 else None

Dijkstra : push (dist[u] + w, v)   key = whole PATH cost from the source   -> cheapest path A -> B
Prim     : push (w, v)             key = the single EDGE into the tree     -> cheapest tree over ALL

start from point 0 (cost 0)
  tree {0}            cheapest way out: 0-1 = 4        take 1   total  4
  tree {0,1}          cheapest way out: 1-3 = 3        take 3   total  7
  tree {0,1,3}        cheapest way out: 3-4 = 4        take 4   total 11
  tree {0,1,3,4}      cheapest way out: 1-2 = 9        take 2   total 20
  all 5 points in the tree -> 20

# python
# LC 1584 - Min Cost to Connect All Points
# IDEA: Prim + min-heap on the implicit complete graph
# time = O(n^2 log n), space = O(n^2)
import heapq

class Solution:
    def minCostConnectPoints(self, points):
        n = len(points)
        in_tree = set()
        min_heap = [(0, 0)]             # (cost to join this point, point index)
        total_cost = 0

        while len(in_tree) < n:
            cost, point = heapq.heappop(min_heap)
            if point in in_tree:
                continue                # only the FIRST (cheapest) pop joins the tree
            in_tree.add(point)
            total_cost += cost

            x1, y1 = points[point]
            for other in range(n):
                if other not in in_tree:
                    x2, y2 = points[other]
                    heapq.heappush(min_heap, (abs(x1 - x2) + abs(y1 - y2), other))

        return total_cost

// java
// LC 1584 - Min Cost to Connect All Points
// IDEA: Prim + min-heap on the implicit complete graph
// time = O(n^2 log n), space = O(n^2)
public int minCostConnectPoints(int[][] points) {
    int n = points.length;
    boolean[] inTree = new boolean[n];
    PriorityQueue<int[]> minHeap = new PriorityQueue<>((x, y) -> Integer.compare(x[0], y[0]));
    minHeap.offer(new int[]{0, 0});              // {cost to join, point index}
    int totalCost = 0;
    int joined = 0;

    while (joined < n) {
        int[] top = minHeap.poll();
        int point = top[1];
        if (inTree[point]) {
            continue;
        }
        inTree[point] = true;
        totalCost += top[0];
        joined++;
        for (int other = 0; other < n; other++) {
            if (!inTree[other]) {
                int dist = Math.abs(points[point][0] - points[other][0])
                         + Math.abs(points[point][1] - points[other][1]);
                minHeap.offer(new int[]{dist, other});
            }
        }
    }
    return totalCost;
}

# python
# LC 1584 - Min Cost to Connect All Points
# IDEA: Prim with a min_dist array instead of a heap (dense graph)
# time = O(n^2), space = O(n)
class Solution:
    def minCostConnectPoints(self, points):
        n = len(points)
        INF = float("inf")
        min_dist = [INF] * n            # cheapest edge from the tree to each point
        in_tree = [False] * n
        min_dist[0] = 0
        total_cost = 0

        for _ in range(n):
            # the outside point closest to the tree
            closest = -1
            for i in range(n):
                if not in_tree[i] and (closest == -1 or min_dist[i] < min_dist[closest]):
                    closest = i
            in_tree[closest] = True
            total_cost += min_dist[closest]

            # the new tree point may offer a cheaper edge to the points still outside
            x1, y1 = points[closest]
            for i in range(n):
                if not in_tree[i]:
                    distance = abs(x1 - points[i][0]) + abs(y1 - points[i][1])
                    if distance < min_dist[i]:
                        min_dist[i] = distance

        return total_cost

// java
// LC 1584 - Min Cost to Connect All Points
// IDEA: Prim with a minDist array instead of a heap (dense graph)
// time = O(n^2), space = O(n)
public int minCostConnectPointsDense(int[][] points) {
    int n = points.length;
    int[] minDist = new int[n];                  // cheapest edge from the tree to each point
    boolean[] inTree = new boolean[n];
    Arrays.fill(minDist, Integer.MAX_VALUE);
    minDist[0] = 0;
    int totalCost = 0;

    for (int round = 0; round < n; round++) {
        // the outside point closest to the tree
        int closest = -1;
        for (int i = 0; i < n; i++) {
            if (!inTree[i] && (closest == -1 || minDist[i] < minDist[closest])) {
                closest = i;
            }
        }
        inTree[closest] = true;
        totalCost += minDist[closest];

        // the new tree point may offer a cheaper edge to the points still outside
        for (int i = 0; i < n; i++) {
            if (!inTree[i]) {
                int distance = Math.abs(points[closest][0] - points[i][0])
                             + Math.abs(points[closest][1] - points[i][1]);
                if (distance < minDist[i]) {
                    minDist[i] = distance;
                }
            }
        }
    }
    return totalCost;
}

# python
# LC 1135 - Connecting Cities With Minimum Cost
# IDEA: Kruskal (template 1-1), cities shifted to 0-indexed
# time = O(E log E), space = O(n + E)
class Solution:
    def minimumCost(self, n, connections):
        edges = [(cost, a - 1, b - 1) for a, b, cost in connections]
        return kruskal(n, edges)        # -1 when fewer than n - 1 edges join

n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]

virtual edges: 0-1 (1)  0-2 (2)  0-3 (2)
pipe edges   : 1-2 (1)  2-3 (1)

Kruskal: 0-1 (1) take, 1-2 (1) take, 2-3 (1) take -> 3 edges for 4 nodes -> cost 3

# python
# LC 1168 - Optimize Water Distribution in a Village
# IDEA: Kruskal + virtual node 0 (a well == a pipe from node 0)
# time = O((n + m) log (n + m)), space = O(n + m)
class Solution:
    def minCostToSupplyWater(self, n, wells, pipes):
        edges = [(cost, 0, house + 1) for house, cost in enumerate(wells)]
        for a, b, cost in pipes:
            edges.append((cost, a, b))
        return kruskal(n + 1, edges)    # n houses + the water source

# python
# LC 1489 - Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
# IDEA: Kruskal with one edge excluded / forced, compared with the true MST weight
# time = O(E^2 * α(V)), space = O(V + E)
class Solution:
    def findCriticalAndPseudoCriticalEdges(self, n, edges):
        # keep the original index: the answer is reported by it
        order = sorted(range(len(edges)), key=lambda i: edges[i][2])

        def mst_weight(skip, force):
            parent = list(range(n))
            size = [1] * n

            def find(x):
                while parent[x] != x:
                    parent[x] = parent[parent[x]]
                    x = parent[x]
                return x

            def union(a, b):
                root_a, root_b = find(a), find(b)
                if root_a == root_b:
                    return False
                if size[root_a] < size[root_b]:
                    root_a, root_b = root_b, root_a
                parent[root_b] = root_a     # union by size keeps the α(V) bound
                size[root_a] += size[root_b]
                return True

            weight = 0
            used = 0
            if force != -1:
                a, b, w = edges[force]
                union(a, b)
                weight += w
                used += 1
            for i in order:
                if i == skip:
                    continue
                a, b, w = edges[i]
                if union(a, b):
                    weight += w
                    used += 1
            return weight if used == n - 1 else float("inf")

        best = mst_weight(-1, -1)
        critical, pseudo = [], []
        for i in range(len(edges)):
            if mst_weight(i, -1) > best:
                critical.append(i)
            elif mst_weight(-1, i) == best:
                pseudo.append(i)
        return [critical, pseudo]

// java
// LC 1489 - Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
// IDEA: Kruskal with one edge excluded / forced, compared with the true MST weight
// time = O(E^2 * α(V)), space = O(V + E)
public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
    // sort edge INDICES by weight: the answer is reported by original index
    Integer[] order = new Integer[edges.length];
    for (int i = 0; i < edges.length; i++) {
        order[i] = i;
    }
    Arrays.sort(order, (x, y) -> Integer.compare(edges[x][2], edges[y][2]));

    int best = mstWeight(n, edges, order, -1, -1);
    List<Integer> critical = new ArrayList<>();
    List<Integer> pseudo = new ArrayList<>();
    for (int i = 0; i < edges.length; i++) {
        if (mstWeight(n, edges, order, i, -1) > best) {
            critical.add(i);
        } else if (mstWeight(n, edges, order, -1, i) == best) {
            pseudo.add(i);
        }
    }
    return Arrays.asList(critical, pseudo);
}

// MST weight with edge `skip` left out and edge `force` taken first; MAX_VALUE if disconnected
private int mstWeight(int n, int[][] edges, Integer[] order, int skip, int force) {
    int[] parent = new int[n];
    int[] size = new int[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        size[i] = 1;
    }
    int weight = 0;
    int used = 0;
    if (force != -1) {
        union(parent, size, edges[force][0], edges[force][1]);
        weight += edges[force][2];
        used++;
    }
    for (int i : order) {
        if (i == skip) {
            continue;
        }
        if (union(parent, size, edges[i][0], edges[i][1])) {
            weight += edges[i][2];
            used++;
        }
    }
    return used == n - 1 ? weight : Integer.MAX_VALUE;
}

private boolean union(int[] parent, int[] size, int a, int b) {
    int rootA = find(parent, a);                 // find() from template 1-1
    int rootB = find(parent, b);
    if (rootA == rootB) {
        return false;
    }
    if (size[rootA] < size[rootB]) {
        int tmp = rootA; rootA = rootB; rootB = tmp;
    }
    parent[rootB] = rootA;                       // union by size keeps the α(V) bound
    size[rootA] += size[rootB];
    return true;
}

"connect ALL nodes, minimum total cost"?
├── no: "cheapest route from A to B"            -> shortest path (Dijkstra.md)
└── yes: an MST
    ├── edges given as a list                   -> Kruskal (1-1)
    ├── every pair is an edge (points)          -> Prim, dense array for O(n^2) (2-1)
    ├── "build here OR connect to a neighbour"  -> add a virtual node 0, then Kruskal (2-3)
    ├── "which edges are in every / some MST"   -> Kruskal with one edge excluded / forced (2-4)
    └── "maximise the min / minimise the max"   -> sort + union until connected, or
                                                   binary search + DSU feasibility (2-5)