Minimum Spanning Tree Pattern in Java - Interview Preparation Guide

Minimum spanning tree is the graph pattern for connecting all vertices with the least total edge cost while avoiding cycles. Strong candidates distinguish edge-centric and node-centric thinking, explain why each chosen edge safely expands the tree, and validate connectivity instead of assuming an MST always exists.

Pattern Summary Table

Problem Statement

Given an undirected weighted graph, compute the minimum total cost needed to connect all nodes, or detect that the graph is disconnected.

Pattern Recognition Signals

• Keywords in the problem: connect all nodes, minimum total cost, spanning tree, no cycles.
• Structural signal: each chosen edge must connect two previously separate regions of the graph.
• Complexity signal: the optimized version avoids repeated rescans, recomputation, or state explosion that brute force would suffer.

Java Template

public int kruskalMST(int n, int[][] edges) {
    Arrays.sort(edges, Comparator.comparingInt(a -> a[2]));
    DSU dsu = new DSU(n);
    int cost = 0, used = 0;
    for (int[] e : edges) {
        if (dsu.union(e[0], e[1])) {
            cost += e[2];
            if (++used == n - 1) break;
        }
    }
    return used == n - 1 ? cost : -1;
}

Dry Run (Kruskal)

Edges (u,v,w) sorted by weight:

(0,1,1), (1,2,2), (0,2,3), (2,3,4)

Process:

1. take (0,1,1) -> components merge, cost=1
2. take (1,2,2) -> merge, cost=3
3. skip (0,2,3) -> would form cycle
4. take (2,3,4) -> merge, cost=7

Used edges = n-1, MST cost = 7.

Kruskal vs Prim

• Kruskal: edge-centric, great with edge list + DSU
• Prim: node-centric, great with adjacency list + priority queue

Rule of thumb:

• sparse edge list input -> Kruskal
• dense adjacency graph or incremental expansion view -> Prim

Both are O(E log E) / O(E log V) scale depending on representation.

Disconnected Graph Handling

MST exists only if graph is fully connected. Always validate:

return used == n - 1 ? cost : -1;

Skipping this check returns incorrect partial-forest cost.

Problem 1: Minimum Cost to Connect All Nodes

Problem description: Given a connected weighted undirected graph, return the total weight of its minimum spanning tree, or -1 if the graph is disconnected.

What we are solving actually: We need one cheapest edge set that connects every node without cycles. The hidden challenge is expanding the tree only with edges that add a brand-new node.

What we are doing actually:

1. Start Prim’s algorithm from any node.
2. Use a min-heap to always choose the cheapest edge leaving the current tree.
3. Ignore edges that point to already-included nodes.
4. Count cost only when an edge truly expands the tree.

public int minimumSpanningTreeCost(int n, List<List<int[]>> graph) {
    boolean[] used = new boolean[n];
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    pq.offer(new int[]{0, 0}); // {node, edgeWeight} with a zero-cost virtual start edge.

    int cost = 0;
    int seen = 0;
    while (!pq.isEmpty() && seen < n) {
        int[] cur = pq.poll();
        int u = cur[0], w = cur[1];
        if (used[u]) continue; // Skip stale edges that point back into the existing tree.

        used[u] = true;
        cost += w; // The cheapest edge that reaches a new node becomes part of the MST.
        seen++;

        for (int[] edge : graph.get(u)) {
            int v = edge[0], weight = edge[1];
            if (!used[v]) pq.offer(new int[]{v, weight}); // Offer every outward edge from the growing tree.
        }
    }
    return seen == n ? cost : -1; // If some node was never reached, one spanning tree does not exist.
}

Debug steps:

• print heap entries as {node, weight} to confirm the cheapest outgoing edge is chosen next
• test one disconnected graph to ensure the method returns -1
• verify the invariant that cost only grows when seen grows

Problem-Fit Checklist

• Identify whether input size or query count requires preprocessing or specialized data structures.
• Confirm problem constraints (sorted input, non-negative weights, DAG-only, immutable array, etc.).
• Validate that the pattern gives asymptotic improvement over brute-force under worst-case input.
• Define explicit success criteria: value only, index recovery, count, path reconstruction, or ordering.

Invariant and Reasoning

• Write one invariant that must stay true after every transition (loop step, recursion return, or update).
• Ensure each step makes measurable progress toward termination.
• Guard boundary states explicitly (empty input, singleton, duplicates, overflow, disconnected graph).
• Add a quick correctness check using a tiny hand-worked example before coding full solution.

Complexity and Design Notes

• Compute time complexity for both preprocessing and per-query/per-update operations.
• Track memory overhead and object allocations, not only Big-O notation.
• Prefer primitives and tight loops in hot paths to reduce GC pressure in Java.
• If multiple variants exist, choose the one with the simplest correctness proof first.

Production Perspective

• Convert algorithmic states into explicit metrics (queue size, active nodes, cache hit ratio, relaxation count).
• Add guardrails for pathological inputs to avoid latency spikes.
• Keep implementation deterministic where possible to simplify debugging and incident analysis.
• Separate pure algorithm logic from I/O and parsing so the core stays testable.

Implementation Workflow

1. Implement the minimal correct template with clear invariants.
2. Add edge-case tests before optimizing.
3. Measure complexity-sensitive operations on realistic input sizes.
4. Refactor for readability only after behavior is locked by tests.

Common Mistakes

1. Choosing the pattern without proving problem fit.
2. Ignoring edge cases (empty input, duplicates, overflow, disconnected state).
3. Mixing multiple strategies without clear invariants.
4. No complexity analysis against worst-case input.

Practice Set (Recommended Order)

1. Min Cost to Connect All Points (LC 1584)
   LeetCode
2. Connecting Cities With Minimum Cost (LC 1135)
   LeetCode

Key Takeaways

• This pattern is most effective when transitions are explicit and invariants are enforced at every step.
• Strong preconditions and boundary handling make these implementations production-safe.
• Reuse this template and adapt it per problem constraints.