Minimum Spanning Tree

A minimum spanning tree is

• a tree, meaning it has no cycle
• minimum, meaning it has minimum weight
• spanning, meaning it connects all nodes

MST Problem

The MST problem takes a connected graph $G$ and outputs an MST for that graph.

Approach: Greedy

The approach is to try to add the smallest edges as long as they do not create a cycle; add an edge to the tree that is minimum across the cut of $T$ vs. $V-T$

Given the MST of $V_{n-m}=v_{1},v_{2},\ldots ,v_{n-m}$, the MST of $V$ should be that of $V_{n-1}$ plus the edge that connects to $v_{n}$ that is the shortest.

$OPT(n)=OPT(n-1)+min((v_{i},v_{n})\in E)$

Implementation

MST(G):
    mst_nodes = start_node
    mst = adjacency list with no edges
    # candidate_edges is a min heap
    candidate_edges = (start_node, G[start_node])
    while mst_nodes is not spanning:
        new_edge = candidate_edges.pop()