A undirected graph $G$ is a graph with:

Review of encoding of undirected graph:

Weighted edges

Let $G$ be an undirected graph. Consider that we have weights on the edges:

$$ w: E(G) \to \mathbb{R}^+ $$

Namely, the function $w$ maps edges to strictly positive real numbers.



We can use the distance between vertices as the weight:

$w(\{u, v\}) = d(\mathrm{pos}(u), \mathrm{pos}(v))$

where $\mathrm{pos}$ is the 2D position of the vertex.

The Minimal Spanning Tree (MST) Problem

Definition Spanning tree

A tree $T$ is called a spanning tree of $G$ if

  • $T$ is fully connected, and

  • $V(T) = V(G)$

Definition Minimal spanning tree (MST)

Let the weight of a graph $$w(H) = \sum_{e\in E(H)} w(e)$$

A MST, $T$, of a graph $G$ is a spanning tree of $G$ with the smallest possible $w(T)$.


! Not a spanning tree


! A (minimal) spanning tree

Algorithms to compute MST


Prim’s algorithm


Let $G$ be an undirected graph, with edge weights given by $w$. Let $r$ be a vertex in $V(G)$.

Compute a MST $T$ starting with $r$.

def prim(G, w, r):

We represent $T$ as a set of edges.

! Why don’t we need to remember the vertices of $T$?


Definition Minimal cut

Let $X\subseteq V(G)$ be a set of vertices in $G$. The minimal cut is an edge ${u, v}\in E(G)$ such that $u\in X$ and $v\not\in X$ with the smallest weight.

! There may be non-unique minimal cuts.



If $S$ is a subtree of a MST, and let $e$ be a minimal cut of $V(S)$, then $S\cup{e}$ is also a subtree of a MST.



Start with just a root $X = {r}$, and keep adding minimal cuts of $X$.

def prim(G, w, r):
    n = G.count_nodes()
    X = set([r])
    T = set([])
    for i in range(n-1):
        (u, v) = minimal_cut(G, X)
        X.add(u, v)
        T.add((u, v))

    return T

! Warning: what happens if $G$ is not fully connected?

Kruskal’s algorithm

Find a MST by computing its edges.

def kruskal(G, w):



Let $R$ and $S$ be two disjoin subtrees of a MST. If there exists an edge $\{u, v\}$ that is a minimal cut of $S$, and $u\in V(S)$ and $v\in V(R)$, then $R\cup S$ is also a subtree of a MST.


Start with lots of small subtrees of a MST, and merge them with minimal cuts until we end up with just one tree that covers all the nodes.



  1. Every vertex by itself is a subtree of a MST (trivially).

  2. The smallest edge is always a minimal cut.

  3. Represent subtree by its vertices.


Definition: Partition

A partition of the vertices of $G$ is a collection of sets of vertices $P = \{X_1, X_2, \dots X_n\}$, such that:

  1. They are all pairwise disjoint.
  2. Every vertex in $G$ appears in exactly one of the $\{X_i\}$.
  3. None of the $X_i$ is empty.

Operations on a parition P:

i = find_partition(P, v)

! Finds the index such that $v\in X_i$

join_partition(P, i, j)

! Replace $X_i, X_j$ from P, with $X_i\cup X_j$


def kruskal(G, w):
    T = set([])
    E = sorted(G.edges(), key=w)
    P = [set([v]) for v in G.nodes()]
    for e in E:
        (u, v) = e
        i = find_partition(P, u)
        j = find_partition(P, v)
        if not i == j:
            join_partition(P, i, j)
        if len(P) == 1:
    return T            






Prim’s algorithm starts with a specific vertex, and grows the MST by computing minimal cuts.

Kruskal’s algorithm starts with $n$ subtrees, and uses the edges with the smallest weights to join them together, eventually into a single MST.

Special topics


! We will go through the code and the networkx library that it uses to draw the graphs in the lab.

© KEN PU, 2016