Anusha Murali

Logo

Please see github.com/anusha-murali for all of my repositories.

View GitHub Profile

Minimum Spanning Tree (MST)

Motivating Problem

We can model the above problem as a graph:

A tree is connected, acyclic, and has $|V|-1$ edges (any two implies the third).

A spanning tree is a subgraph of a connected, undirected graph that includes all the vertices of the graph.

A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together without any cycles and with the minimum possible total edge weight.

An MST is a spanning tree whose sum of edge weights is as small as possible.

Example: In the following example, there is more than one MST. (Replace edge $(e, f)$ with $(c,e)$).

mst1

Properties of an MST

Building an MST

Generic MST Algorithm

    def genericMST(G, w)
        A = []
        while A does not form a spanning tree:
            find an edge (u,v) that is safe for A
            A.append({u,v})
        return A

We can use the loop invariant to show that this generic algorithm works.

How to find a safe edge?

Consider an arbitrary edge $(u, v) \in E$. Let $S \subset V$ be any proper subset of vertices that includes $u$, but not $v$. In other words $v \in V - S$. In any MST, there has to be one edge (at least) that connects $S$ with $V-S$. Therefore, intuitively, we must choose the edge between $S$ and $V-S$ such that it has the minimum weight.

Let $A \in E$ a set that grows to become an MST (Please see the above function genericMST()).

Cut Property: For any cut of a connected, undirected graph, the minimum weight edge that crosses the cut belongs to MST.

Theorem: Let $A$ be a subset of some MST, $(S, V - S)$ be a cut that respects $A$, and $(u, v)$ be a light edge crossing $(S, V-S)$. Then $(u,v)$ is safe for $A$.

Proof: Let $T$ be an MST that includes $A$.

If $T$ contains $(u, v)$, we’re done.

So, let’s assume that $T$ does not contain $(u,v)$. Construct a different MST $T’$ that includes $A \cup {(u,v)}$.

Recall: a tree has unique path between each pair of vertices. Since $T$ is an MST, it contains a unique path $p$ between $u$ and $v$. Path $p$ must cross the cut $(S, V-S)$ at least once. Let $(x, y)$ be an edge of $p$ that crosses the cut. From how we chose $(u,v)$, we know that $w(u,v) \leq w(x, y)$.

mst2

Since the cut respects $A$, edge $(x, y)$ is not in $A$.

To form $T’$ from $T$

So, $T’ = T - {(x,y)} \cup {(u,v)}$.

$T’$ is a spanning tree. It’s weight is $w(T’) = w(T) - w(x, y) + w(u,v) \leq w(T)$ since $w(u,v) \leq w(x,y)$.

Since $T’$ is a spanning tree, $w(T’) \leq w(T)$, and $T$ is an MST, then $T’$ must be an MST.

We will now show that $(u,v)$ is safe for $A$.

Two popular algorithms for finding MST in a graph are:

  1. Kruskal’s MST Algorithm
  2. Prim’s MST Algorithm

Back to Greedy Algorithms

Data Structures and Algorithms Table of Contents


anusha-murali.github.io