Graph Algorithms

Minimum Spanning Trees

The cheapest set of edges that connects every vertex with no cycles — Prim's grows one tree outward, Kruskal's grows a forest from cheapest edges inward, and both are provably optimal despite being purely greedy.

An MST connects V vertices using exactly V − 1 edges at minimum total weight
Prim's: grow one tree from a start vertex, always adding the cheapest edge crossing the frontier — structurally identical to Dijkstra
Kruskal's: sort all edges, add each one unless it would form a cycle — needs union-find for the cycle check
Both are greedy and both are correct, justified by the cut property: the cheapest edge crossing any cut belongs to some MST
The MST is unique only if all edge weights are distinct; with ties, multiple different MSTs can share the same minimum total weight

Kruskal's algorithm with union-find

static long kruskalMST(int n, int[][] edges) {   // edges[i] = {u, v, weight}
    Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));
    UnionFind uf = new UnionFind(n);
    long totalWeight = 0;
    int edgesUsed = 0;
    for (int[] e : edges) {
        if (uf.union(e[0], e[1])) {       // true only if u, v were in different components
            totalWeight += e[2];
            if (++edgesUsed == n - 1) break;
        }
    }
    return totalWeight;
}

Prim's vs Kruskal's
	Prim's	Kruskal's
Grows	one tree, outward from a start vertex	a forest, merging components as edges are added
Needs	a priority queue over frontier edges	sorted edges + union-find
Best on	dense graphs (many edges, adjacency matrix)	sparse graphs (edge list is small relative to V²)