Minimum Spanning Tree

    DSA · Advanced

    Definition

    An MST connects all vertices with minimum total edge weight and no cycles (Kruskal or Prim).

    Used in network design, clustering and road planning.

    Diagram

    A-B 1B-C 2A-C 3 (skip)total 3

    Flowchart

    Sort edges by weightTake smallest edgeSkip if it forms a cycle (Union-Find)Stop at V−1 edges

    Example: Kruskal

    edges = [(1, 0, 1), (2, 1, 2), (3, 0, 2)]
p = [0, 1, 2]
def f(x):
    while p[x] != x: x = p[x]
    return x
tot = 0
for w, a, b in sorted(edges):
    if f(a) != f(b):
        p[f(a)] = f(b); tot += w
print(tot)

    Output: 3

    Complexity

    Kruskal O(E log E) · Prim O(E log V)

    Key points

    • MST has V−1 edges
    • Prim is better for dense graphs

    Interview questions

    Kruskal vs Prim?

    Kruskal grows by edges globally; Prim grows one tree from a start vertex.

    More DSA topics

    ArraysLinked ListStackQueue