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 [math]k_v \in \mathbb{R}[/math] for each node [math]v \in V[/math].
2. A priority queue [math]Q[/math] of nodes. The key of a node [math]v[/math] for [math]Q[/math] is [math]k_v[/math], the information is one of the edges of [math]G[/math] that is incident to [math]v[/math].

Abstract view

Invariant: After [math]i \geq 0[/math] iterations:

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

Note that, once a node joins [math]V_i[/math], its key will be irrelevant for the rest of the algorithm.

Variant: [math]i[/math] increases by [math]1[/math].

Break condition: [math]i = n - 1[/math]; then return [math]E_{n-1}[/math].

Induction basis

Abstract view:

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

Implementation: Obvious.

Proof: Obvious.

Induction step

Abstract view:

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

Implementation: Obvious.

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

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

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

Complexity

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

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