Minimum Spanning Tree

Let $G = (V, E)$ be an undirected graph.

A spanning tree $T = (V, F)$ of $G$ is a graph containing the same vertices as $G$ , and $|V| - 1$ edges (called $F$ ) of $G$ that form a tree. (There there is exactly one path between any two vertices of $T$ .)

If $G$ is not connected, it has no spanning tree, but we can instead compute a spanning forest, or collection of spanning trees, having one tree for each connected component of $G$ .

If $G$ is weighted, then a minimum spanning tree $T$ of $G$ is a spanning tree of $G$ whose total weight (summed over all edges of $T$ ) is minimal. In other words, no other spanning tree of $G$ has a smaller total weight.

Kruskal’s algorithm computes the minimum spanning tree of $G$ as follows:
- Create a new graph $T$ with the same vertices as $G$ , but no edges (yet).
- Make a list of all the edges in $G$ .
- Sort the edges by weight, from least to greatest.
- Iterate through the edges in sorted order.
  
  For each edge $(v, w)$ : if $v$ and $w$ are not connected by a path in T, add $(v, w)$ to $T$ .
Since Kruskal’s algorithm never adds $(v, w)$ if some other path already connects $v$ and $w$ , $T$ is guaranteed to be a tree (if $G$ is connected) or a forest (if $G$ is not).

Sorting the edges takes $O(|E| \log |E|)$ time. To determining whether two edges are already connected by a path, we can use disjoint sets, so that all the iterations of the look take less than $O(|E| \log |E|)$ time.
The running time of Kruskal’s algorithm is $O(|V| + |E| \log |E|)$ on adjacency lists and $O(|V|^2 + |E| \log |E|)$ on adjacency matrix (it takes $\Theta(|V|^2)$ time to make a list of all the edges).

Since we use adjacency lists when $|E| < |V|^2$ , $\log |E| < 2 \log |V|$ , so we can also say that the running time of Kruskal’s algorithm for adjacency lists is $O(|V| + |E| \log |V|)$ .
Visualization:

Prim’s algorithm computes the minimum spanning tree of $G$ as follows:
- For all $v$ in $V$ , set $v.distance = \inf$ , $v.parent = nil$ .
- Create a new graph $T$ with the same vertices as $G$ , but no edges (yet).
- Choose a vertex $s$ from $V$ . Set $s.distance = 0$ .
- Make a priority queue $Q$ of all the vertices, with distance as the priority.
- While $Q$ is not empty:
  - $v = Q.removeMin$
  - Add the edge $(v, v.parent)$ to $T$ .
  - For each vertex $w$ such that $e = (v,w) \in E$ and $w \in Q$ :
    
    if $e.weight < w.distance$ , set $w.distance = e.weight$ and $w.parent = v$ .
We begin with a single root vertex $r$ , and add edges connecting new vertices until they are all connected. We’ll use a “distance” variable for each vertex to keep track of the shortest edge so far for joining that vertex to the result tree T. We’ll also track which edge that is.
The total time for $|V|$ removeMin operations will be in $O(|V| \log |V|)$ . The total time for $|E|$ updatePriority operations will be in $O(|E| \log |V |)$ . So the total running time is in $O((|V| + |E|) \log |V|)$ , which is $O(|E| \log |V|)$ .

results matching ""