Skip to content

23.2 The algorithms of Kruskal and Prim

23.2-1

Kruskal's algorithm can return different spanning trees for the same input graph $G$, depending on how it breaks ties when the edges are sorted into order. Show that for each minimum spanning tree $T$ of $G$, there is a way to sort the edges of $G$ in Kruskal's algorithm so that the algorithm returns $T$.

Suppose that we wanted to pick $T$ as our minimum spanning tree. Then, to obtain this tree with Kruskal's algorithm, we will order the edges first by their weight, but then will resolve ties in edge weights by picking an edge first if it is contained in the minimum spanning tree, and treating all the edges that aren't in $T$ as being slightly larger, even though they have the same actual weight.

With this ordering, we will still be finding a tree of the same weight as all the minimum spanning trees $w(T)$. However, since we prioritize the edges in $T$, we have that we will pick them over any other edges that may be in other minimum spanning trees.

23.2-2

Suppose that we represent the graph $G = (V, E)$ as an adjacency matrix. Give a simple implementation of Prim's algorithm for this case that runs in $O(V^2)$ time.

At each step of the algorithm we will add an edge from a vertex in the tree created so far to a vertex not in the tree, such that this edge has minimum weight. Thus, it will be useful to know, for each vertex not in the tree, the edge from that vertex to some vertex in the tree of minimal weight. We will store this information in an array $A$, where $A[u] = (v, w)$ if $w$ is the weight of $(u, v)$ and is minimal among the weights of edges from $u$ to some vertex $v$ in the tree built so far. We'll use $A[u].1$ to access $v$ and $A[u].2$ to access $w$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
PRIM-ADJ(G, w, r)
    initialize A with every entry = (NIL, )
    T = {r}
    for i = 1 to V
        if Adj[r, i] != 0
            A[i] = (r, w(r, i))
    for each u in V - T
        k = min(A[i].2)
        T = T  {k}
        k.π = A[k].1
        for i = 1 to V
            if Adf[k, i] != 0 and Adj[k, i] < A[i].2
                A[i] = (k, Adj[k, i])

23.2-3

For a sparse graph $G = (V, E)$, where $|E| = \Theta(V)$, is the implementation of Prim's algorithm with a Fibonacci heap asymptotically faster than the binary-heap implementation? What about for a dense graph, where $|E| = \Theta(V^2)$? How must the sizes $|E|$ and $|V|$ be related for the Fibonacci-heap implementation to be asymptotically faster than the binary-heap implementation?

Prim's algorithm implemented with a Binary heap has runtime $O((V + E)\lg V)$, which in the sparse case, is just $O(V\lg V)$. The implementation with Fibonacci heaps is

$$O(E + V\lg V) = O(V + V\lg V) = O(V \lg V).$$

  • In the sparse case, the two algorithms have the same asymptotic runtimes.
  • In the dense case.

    • The binary heap implementation has a runtime of

      $$O((V + E)\lg V) = O((V + V^2)\lg V) = O(V^2\lg V).$$

    • The Fibonacci heap implementation has a runtime of

      $$O(E + V\lg V) = O(V^2 + V\lg V) = O(V^2).$$

    So, in the dense case, we have that the Fibonacci heap implementation is asymptotically faster.

  • The Fibonacci heap implementation will be asymptotically faster so long as $E = \omega(V)$. Suppose that we have some function that grows more quickly than linear, say $f$, and $E = f(V)$.

  • The binary heap implementation will have runtime of

    $$O((V + E)\lg V) = O((V + f(V))\lg V) = O(f(V)\lg V).$$

However, we have that the runtime of the Fibonacci heap implementation will have runtime of

$$O(E + V\lg V) = O(f(V) + V\lg V).$$

This runtime is either $O(f(V))$ or $O(V\lg V)$ depending on if $f(V)$ grows more or less quickly than $V\lg V$ respectively.

In either case, we have that the runtime is faster than $O(f(V)\lg V)$.

23.2-4

Suppose that all edge weights in a graph are integers in the range from $1$ to $|V|$. How fast can you make Kruskal's algorithm run? What if the edge weights are integers in the range from $1$ to $W$ for some constant $W$?

We know that Kruskal's algorithm takes $O(V)$ time for initialization, $O(E\lg E)$ time to sort the edges, and $O(E\alpha(V))$ time for the disjoint-set operations, for a total running time of $O(V + E\lg E + E\alpha(V)) = O(E\lg E)$.

If we knew that all of the edge weights in the graph were integers in the range from $1$ to $|V|$, then we could sort the edges in $O(V + E)$ time using counting sort. Since the graph is connected, $V = O(E)$, and so the sorting time is reduced to $O(E)$. This would yield a total running time of $O(V + E + E\alpha(V)) = O(E\alpha(V))$, again since $V = O(E)$, and since $E = O(E\alpha(V))$. The time to process the edges, not the time to sort them, is now the dominant term. Knowledge about the weights won't help speed up any other part of the algorithm, since nothing besides the sort uses the weight values.

If the edge weights were integers in the range from $1$ to $W$ for some constant $W$, then we could again use counting sort to sort the edges more quickly. This time, sorting would take $O(E + W) = O(E)$ time, since $W$ is a constant. As in the first part, we get a total running time of $O(E\alpha(V))$.

23.2-5

Suppose that all edge weights in a graph are integers in the range from $1$ to $|V|$. How fast can you make Prim's algorithm run? What if the edge weights are integers in the range from $1$ to $W$ for some constant $W$?

The time taken by Prim's algorithm is determined by the speed of the queue operations. With the queue implemented as a Fibonacci heap, it takes $O(E + V\lg V)$ time.

Since the keys in the priority queue are edge weights, it might be possible to implement the queue even more efficiently when there are restrictions on the possible edge weights.

We can improve the running time of Prim's algorithm if $W$ is a constant by implementing the queue as an array $Q[0..W + 1]$ (using the $W + 1$ slot for $\text{key} = \infty$), where each slot holds a doubly linked list of vertices with that weight as their key. Then $\text{EXTRACT-MIN}$ takes only $O(W) = O(1)$ time (just scan for the first nonempty slot), and $\text{DECREASE-KEY}$ takes only $O(1)$ time (just remove the vertex from the list it's in and insert it at the front of the list indexed by the new key). This gives a total running time of $O(E)$, which is the best possible asymptotic time (since $\Omega(E)$ edges must be processed).

However, if the range of edge weights is $1$ to $|V|$, then $\text{EXTRACT-MIN}$ takes $\Theta(V)$ time with this data structure. So the total time spent doing $\text{EXTRACT-MIN}$ is $\Theta(V^2)$, slowing the algorithm to $\Theta(E + V^2) = \Theta(V^2)$. In this case, it is better to keep the Fibonacci-heap priority queue, which gave the $\Theta(E + V\lg V)$ time.

Other data structures yield better running times:

  • van Emde Boas trees (see Chapter 20) give an upper bound of $O(E + V\lg\lg V)$ time for Prim's algorithm.
  • A redistributive heap (used in the single-source shortest-paths algorithm of Ahuja, Mehlhorn, Orlin, and Tarjan, and mentioned in the chapter notes for Chapter 24) gives an upper bound of $O(E + V \sqrt{\lg V})$ for Prim's algorithm.

23.2-6 $\star$

Suppose that the edge weights in a graph are uniformly distributed over the halfopen interval $[0, 1)$. Which algorithm, Kruskal's or Prim's, can you make run faster?

For input drawn from a uniform distribution I would use bucket sort with Kruskal's algorithm, for expected linear time sorting of edges by weight. This would achieve expected runtime $O(E\alpha(V))$.

23.2-7 $\star$

Suppose that a graph $G$ has a minimum spanning tree already computed. How quickly can we update the minimum spanning tree if we add a new vertex and incident edges to $G$?

We start with the following lemma.

Lemma

Let $T$ be a minimum spanning tree of $G = (V, E)$, and consider a graph $G' = (V', E')$ for which $G$ is a subgraph, i.e., $V \subseteq V'$ and $E \subseteq E'$. Let $\overline T = E - T$ be the edges of $G$ that are not in $T$. Then there is a minimum spanning tree of $G'$ that includes no edges in $\overline T$.

Proof

By Exercise 23.2-1, there is a way to order the edges of $E$ so that Kruskal's algorithm, when run on $G$, produces the minimum spanning tree $T$. We will show that Kruskal's algorithm, run on $G'$, produces a minimum spanning tree $T'$ that includes no edges in $\overline T$. We assume that the edges in $E$ are considered in the same relative order when Kruskal's algorithm is run on $G$ and on $G'$. We first state and prove the following claim.

Claim

For any pair of vertices $u, v \in V$, if these vertices are in the same set after Kruskal's algorithm run on $G$ considers any edge $(x, y) \in E$, then they are in the same set after Kruskal's algorithm run on $G'$ considers $(x, y)$.

Proof of claim

Let us order the edges of $E$ by nondecreasing weight as $\langle (x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k) \rangle$, where $k = |E|$. This sequence gives the order in which the edges of $E$ are considered by Kruskal's algorithm, whether it is run on $G$ or on $G'$. We will use induction, with the inductive hypothesis that if $u$ and $v$ are in the same set after Kruskal's algorithm run on $G$ considers an edge $(x_i, y_i)$, then they are in the same set after Kruskal's algorithm run on $G'$ considers the same edge. We use induction on $i$.

Basis: For the basis, $i = 0$. Kruskal's algorithm run on $G$ has not considered any edges, and so all vertices are in different sets. The inductive hypothesis holds trivially.

Inductive step: We assume that any vertices that are in the same set after Kruskal's algorithm run on $G$ has considered edges $\langle (x_1, y_1), (x_2, y_2), \ldots, (x_{i - 1}, y_{i - 1}) \rangle$ are in the same set after Kruskal's algorithm run on $G'$ has considered the same edges. When Kruskal's algorithm runs on $G'$, after it considers $(x_{i - 1}, y_{i - 1})$, it may consider some edges in $E' - E$ before considering $(x_i, y_i)$. The edges in $E' - E$ may cause $\text{UNION}$ operations to occur, but sets are never divided. Hence, any vertices that are in the same set after Kruskal's algorithm run on $G'$ considers $(x_{i - 1}, y_{i - 1})$ are still in the same set when $(x_i, y_i)$ is considered.

When Kruskal's algorithm run on $G$ considers $(x_i, y_i)$, either $x_i$ and $y_i$ are found to be in the same set or they are not.

  • If Kruskal's algorithm run on $G$ finds $x_i$ and $y_i$ to be in the same set, then no $\text{UNION}$ operation occurs. The sets of vertices remain the same, and so the inductive hypothesis continues to hold after considering $(x_i, y_i)$.
  • If Kruskal's algorithm run on $G$ finds $x_i$ and $y_i$ to be in different sets, then the operation $\text{UNION}(x_i, y_i)$ will occur. Kruskal's algorithm run on $G'$ will find that either $x_i$ and $y_i$ are in the same set or they are not. By the inductive hypothesis, when edge $(x_i, y_i)$ is considered, all vertices in $x_i$'s set when Kruskal's algorithm runs on $G$ are in $x_i$'s set when Kruskal's algorithm runs on $G'$, and the same holds for $y_i$. Regardless of whether Kruskal's algorithm run on $G'$ finds $x_i$ and $y_i$ to already be in the same set, their sets are united after considering $(x_i, y_i)$, and so the inductive hypothesis continues to hold after considering $(x_i, y_i)$. (#claim)

With the claim in hand, we suppose that some edge $(u, v) \in \overline T$ is placed into $T'$. That means that Kruskal's algorithm run on $G$ found $u$ and $v$ to be in the same set (since $(u, v) \in \overline T$ ) but Kruskal's algorithm run on $G'$ found $u$ and $v$ to be in different sets (since $(u, v)$ is placed into $T'$). This fact contradicts the claim, and we conclude that no edge in $\overline T$ is placed into $T'$. Thus, by running Kruskal's algorithm on $G$ and $G'$, we demonstrate that there exists a minimum spanning tree of $G'$ that includes no edges in $\overline T$. (#lemma)

We use this lemma as follows. Let $G' = (V', E')$ be the graph $G = (V, E)$ with the one new vertex and its incident edges added. Suppose that we have a minimum spanning tree $T$ for $G$. We compute a minimum spanning tree for $G'$ by creating the graph $G'' = (V', E'')$, where $E''$ consists of the edges of $T$ and the edges in $E' - E$ (i.e., the edges added to $G$ that made $G'$), and then finding a minimum spanning tree $T'$ for $G''$. By the lemma, there is a minimum spanning tree for $G'$ that includes no edges of $E - T$. In other words, $G'$ has a minimum spanning tree that includes only edges in $T$ and $E' - E$ ; these edges comprise exactly the set $E''$. Thus, the the minimum spanning tree $T'$ of $G''$ is also a minimum spanning tree of $G'$.

Even though the proof of the lemma uses Kruskal's algorithm, we are not required to use this algorithm to find $T'$. We can find a minimum spanning tree by any means we choose. Let us use Prim's algorithm with a Fibonacci-heap priority queue. Since $|V'| = |V| + 1$ and $|E''| \le 2|V| - 1$ ($E''$ contains the $|V| - 1$ edges of $T$ and at most $|V|$ edges in $E' - E$ ), it takes $O(V)$ time to construct $G''$, and the run of Prim's algorithm with a Fibonacci-heap priority queue takes time $O(E'' + V'\lg V) = O(V\lg V)$. Thus, if we are given a minimum spanning tree of $G$, we can compute a minimum spanning tree of $G'$ in $O(V\lg V)$ time.

23.2-8

Professor Borden proposes a new divide-and-conquer algorithm for computing minimum spanning trees, which goes as follows. Given a graph $G = (V, E)$, partition the set $V$ of vertices into two sets $V_1$ and $V_2$ such that $|V_1|$ and $|V_2|$ differ by at most $1$. Let $E_1$ be the set of edges that are incident only on vertices in $V_1$, and let $E_2$ be the set of edges that are incident only on vertices in $V_2$. Recursively solve a minimum-spanning-tree problem on each of the two subgraphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$. Finally, select the minimum-weight edge in $E$ that crosses the cut $(V_1, V_2)$, and use this edge to unite the resulting two minimum spanning trees into a single spanning tree.

Either argue that the algorithm correctly computes a minimum spanning tree of $G$, or provide an example for which the algorithm fails.

The algorithm fails. Suppose $E = \{(u, v), (u, w), (v, w)\}$, the weight of $(u, v)$ and $(u, w)$ is $1$, and the weight of $(v, w)$ is $1000$, partition the set into two sets $V_1 = \{u\}$ and $V_2 = \{v, w\}$.