Prim

Chapters
1. [00:00] Einführung
2. [01:27] Der Algorithmus von Prim anhand eines Beispiels
3. [06:59] Korrektheitsbeweis für den Algorithmus von Prim
4. [11:14] Das sieht doch aus wie der Algorithmus von Dijkstra?
5. [12:07] Wie lautet die Invariante?
6. [12:40] Warum ist der Algorithmus korrekt?
7. [13:00] Wie wird die Invariante sichergestellt?
8. [13:47] Was ist die asymptotische Komplexität des Algorithhmus?

General information

Algorithmic problem: Minimum spanning tree

Prerequisites:

Type of algorithm: loop

Auxiliary data:

1. A key $k_v \in \mathbb{R}$ for each node $v \in V$.
2. A priority queue $Q$ of nodes. The key of a node $v$ for $Q$ is $k_v$, the information is one of the edges of $G$ that is incident to $v$.

Abstract view

Invariant: After $i \geq 0$ iterations:

1. There is a node set $V_i$ of size $\vert V_i \vert = i+1$ and an edge set $E_i \subseteq E$ such that $E_i$ solely connects nodes in $V_i$, and $V(V_i,E_i)$ is a tree.
2. There is a minimum spanning tree $(V,E'_i)$ of $G$ such that $E_i \subseteq E'_i$.
3. The key $k_v$ of $v \in V \setminus V_i$ is the minimal length of an edge that connects $v$ with some node in $V_i$ (or $K_v = +\infty$, if there is no such edge). If $v \in Q$ and $K_v \lt +\infty$, this edge is the information associated with $v$ in $Q$.

Note that, once a node joins $V_i$, its key will be irrelevant for the rest of the algorithm.

Variant: $i$ increases by $1$.

Break condition: $i = n - 1$; then return $E_{n-1}$.

Induction basis

Abstract view:

1. Choose an arbitrary node $s \in V$ and set $V_0 := \{s\}$.
2. For each node $v \in V \setminus \{s\}$:
1. If $(s,v) \in E$, set $k_v := \ell((s,v))$, otherwise set $k_v := + \infty$.
2. Insert $v$ with key $k_v$ in $Q$.

Implementation: Obvious.

Proof: Obvious.

Induction step

Abstract view:

1. Extract the first node $v$ from $Q$.
2. Let $e$ denote the edge stored as information for $v$ in $Q$.
3. For each $w \in V \setminus V_{i-1}$ such that $(v,w) \in E$ and $\ell((v,w)) \lt k_w$:
1. Set $(v,w)$ as the new information for $w$ in $Q$.
2. Set $k_w := \ell((v,w))$.
3. Rearrange $Q$ according to the decreased key $k_w$.
4. $E_i := E_{i-1} \cup \{e\}$.
5. $V_i := V_{i-1} \cup \{v\}$.

Implementation: Obvious.

Correctness: The first and third invariants are obviously maintained, so we will focus on the second invariant. Let $u \in V_{i-1}$ denote the other endnode of $e$, so it is $e = (u,v)$.

Since $(V,E'_{i-1})$ is a spanning tree of $G$, there is exactly one path $p$ in $(V,E'_{i-1}$ connecting $u$ and $v$. As $(V,E'_{i-1})$ is cycle-free and contains the tree $(V_{i-1},E_{i-1})$, $p$ contains exactly one edge $e' = (v',w') \in E'_{i-1}$ such that $v' \in V_{i-1}$ and $w' \notin V_{i-1}$. If $e' = e$ (and thus $p = (e)$), the invariant is maintained by $E'_i := E'_{i-1}$. So consider the case that $e' \neq e$.

Note that $e' \in Q$ immediately before the $i$-th iteration. Therefore, the specific choice of implies $\ell(e') \geq \ell(e)$. So, with $E'_i := E'_{i-1} \setminus \{e'\} \cup \{e\}$ we obtain a spanning tree of $G$ whose weight is not larger than that of $(V,E'_{i-1})$, which is minimum by definition.

Complexity

Statement: $\mathcal{O}((n+m) \cdot T(n))$ in the worst case, where $n = \vert V \vert$ and $m = \vert A \vert$ and $T(n)$ is the asymptotic complexity of the methods of $Q$ .

Proof: In the preprocessing, $n - 1$ nodes are to be inserted in $Q$, which takes $\mathcal{O}(n \cdot T(n))$ time. Since each node is inserted at most once, all extraction operations take $\mathcal{O}(n \cdot T(n))$ time, too. For each edge, $Q$ has to be rearranged at most once, which results in $\mathcal{O}(m \cdot T(n))$ time. Clearly, all other operations of the preprocessing and the main loop are dominated by these bounds as well.