Minimum Spanning Tree - rFronteddu/general_wiki GitHub Wiki

Minimum Spanning Tree (MST)

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, undirected graph that spans all the vertices (i.e., connects them) without forming cycles, while minimizing the total edge weight. MSTs are useful in optimizing connections, like wiring electrical components, where you need to minimize the amount of material used.

Problem Setup

  • The graph G = (V,E) represents vertices (V) and edges (E), where edges have weights representing costs.
  • We want to find a tree T, a subset of E, that spans all vertices and has the minimum possible total weight.

Algorithms

Two primary algorithms are commonly used for solving the MST problem:

  1. Kruskal: Builds the MST by adding edges in increasing order of weight, avoiding cycles.
  2. Prim's Algorithm: Grows the MST one vertex at a time, always adding the lightest edge that connects a vertex in the tree to one outside it.

Growing a MST

A generic greedy approach can be used to grow an MST:

  • Initialize an empty set of edges A.
  • Repeatedly find a "safe" edge (an edge that can be added without forming a cycle) and add it to A.
  • Stop once A contains |V|-1 edges (one less than the number of vertices)

Recognizing Safe Edges

An edge is "safe" if it is the lightest edge crossing a cut (a partition of vertices into two sets) that respects the already chosen edges. By adding only safe edges, you ensure the construction of an MST.

Kruskal's Algorithm

  • Start with a forest (disconnected trees), where each vertex is its own tree.
  • Add the lightest edge that connects two different trees.
  • Use the Union-Find data structure to efficiently manage tree merging and cycle detection
  • Time complexity O(E log V)
MST-KRUSKAL(G,w)
    A = {}
    for each v in G.V
        MAKE-SET(V)
    sort G.E in nondecreasing order by weight w
    
    for each (u,v) in G.E, taken in nondecreasing order by weight
        // check whether u,v belong to the same tree i.e. whether we would add a cycle
        if FIND_SET(u) != FIND_SET(v) // FIND_SET returns a representative element from the set that contains u
            add (u,v) to A
            // UNION separates vertices into clusters to determine whether two vertices belong 
            // to the same cluster and hence if adding an edge will produce a cycle
            UNION(u,v) 
    return A

Prim's Algorithm

Prim’s: "I want to connect all cities with the least amount of road."

Prim Algorithm Demo

  • Start from an arbitrary vertex and grow a single tree by repeatedly adding the lightest edge that connects the tree to a new vertex.

  • Use a priority queue (min-heap) to efficiently find the next lightest edge.

  • Time complexity O(E log V)

  • Prim's java implementation

MST-Prim(G, w, r) {
    for u in G.V
        u.w = max
        u.p = nil
    r.w = 0
    Q = G.V
    while Q not empty
        u = ExtractMin(Q)
        for v in G.Adj[u]
            if v in Q and w(u,v) < v.w
                // if it's in Q it's not in the MST yet
                v.p = u
                v.w = w(u,v)
}

Comparison

  • Both have similar time complexity but they work differently: Kruskal operates globally (on all edges), while Prim focuses locally (on growing a tree).

Key Theorem:

For any set of edges A in a MST, the lightest edge crossing any cut that respects A is always safe to add.