Kruskal for maximum spanning forest

Chapters

1. [00:00] Einführung
2. [01:59] Der Algorithmus von Kruskal anhand eines Beispiels
3. [06:56] Und wie ist das bei mehreren Zusammenhangskomponenten?
4. [07:29] Welches Problem löst der Algorithmus von Kruskal genau?
5. [08:05] Wie lautet die Invariante?
6. [08:33] Warum ist der Algorithmus korrekt?
7. [08:59] Wie wird die Invariante sichergestellt?
8. [10:25] Was ist die asymptotische Komplexität des Algorithmus?

General information

Algorithmic problem: Maximum spanning forest

Prerequisites:

Type of algorithm: loop

Auxiliary data:

1. A sorted sequence [math]\displaystyle{ S }[/math] whose items are the edges of [math]\displaystyle{ E }[/math]. The edges are sorted in descending order, that is, the edge [math]\displaystyle{ e \in E }[/math] with the largest value of [math]\displaystyle{ \ell(e) }[/math] is the first element of the sequence (ties arbitrarily broken). Below, [math]\displaystyle{ e_i }[/math] denotes the [math]\displaystyle{ i }[/math]-th edge in [math]\displaystyle{ S }[/math].
2. A union-find data structure [math]\displaystyle{ U F }[/math] on [math]\displaystyle{ V }[/math].

Abstract view

Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations:

1. The undirected graph [math]\displaystyle{ F_i = (V,E_i) }[/math], where [math]\displaystyle{ E_i }[/math] is the set of all selected edges immediately after the [math]\displaystyle{ i }[/math]-th iteration, is cycle-free; in particular, it is maximally cycle-free in the sense that, for [math]\displaystyle{ j \in \{1,...,i\} }[/math], adding an edge [math]\displaystyle{ e_J \notin F_i }[/math] would close a cycle in [math]\displaystyle{ F_i }[/math].
2. For the undirected graph [math]\displaystyle{ F_i = (V,E_i) }[/math], there is a maximum spanning forest [math]\displaystyle{ F_i' = (V,E'_i) }[/math] of [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ E_i \subseteq E'_i }[/math].
3. The sets of [math]\displaystyle{ U F }[/math] are the connected components of [math]\displaystyle{ F_i }[/math].

Variant: [math]\displaystyle{ i }[/math] increases by [math]\displaystyle{ 1 }[/math].

Break condition: [math]\displaystyle{ i = \vert E \vert }[/math].

Induction basis

Abstract view:

1. [math]\displaystyle{ E_0 := \emptyset }[/math]
2. [math]\displaystyle{ U F }[/math] is initialized by [math]\displaystyle{ V }[/math], so each node [math]\displaystyle{ v \in V }[/math] is a singleton in [math]\displaystyle{ U F }[/math].

Implementation: Obvious.

Proof: Nothing to show.

Induction step

Abstract view: If inserting [math]\displaystyle{ e_i }[/math] would close a cycle, reject [math]\displaystyle{ e_i }[/math]; otherwise, insert [math]\displaystyle{ e_i }[/math].

Implementation:

1. Let [math]\displaystyle{ v,w \in V }[/math] denote the endnodes of [math]\displaystyle{ e_i }[/math], that is, [math]\displaystyle{ e_i = \{v,w\} }[/math].
2. If [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w }[/math] belong to different sets in [math]\displaystyle{ U F }[/math]:
   1. Insert [math]\displaystyle{ e_i }[/math] in the result.
   2. Unite the sets of [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w }[/math] in [math]\displaystyle{ U F }[/math].

Correctness: The first and third invariants are obvious. So we focus on the second invariant. We may safely set [math]\displaystyle{ F'_i := F'_{i-1} }[/math] if

1. either [math]\displaystyle{ e_i \in E'_{i-1} }[/math] and [math]\displaystyle{ e_i }[/math] is inserted in the [math]\displaystyle{ i }[/math]-th iteration
2. or [math]\displaystyle{ e_i \notin E'_{i-1} }[/math] and [math]\displaystyle{ e_i }[/math] is rejected in the -th iteration.

Note that the case that [math]\displaystyle{ e_i \in E'_{i-1} }[/math] and [math]\displaystyle{ e_i }[/math] is rejected cannot occur. In fact, [math]\displaystyle{ e_i \in E'_{i-1} }[/math] implies that [math]\displaystyle{ (V,E_{i-1} \cup{\{e_i\}}) }[/math] is cycle-free, but rejecting [math]\displaystyle{ e_i }[/math] implies that [math]\displaystyle{ (V,E_{i-1} \cup{\{e_i\}}) }[/math] contains a cycle. So it remains to consider the case that [math]\displaystyle{ e_i }[/math] is accepted but [math]\displaystyle{ e_i \notin E'_{i-1} }[/math].

As [math]\displaystyle{ \ell(e_i) \gt 0 }[/math] and [math]\displaystyle{ F'_{i-1} }[/math] is maximal, [math]\displaystyle{ (V,E'_{i-1} \cup{\{e_i\}}) }[/math] contains a cycle. Since [math]\displaystyle{ F_{i-1} }[/math] is cycle-free, there must be an edge [math]\displaystyle{ e \in E'_{i-1} \setminus E_{i-1} }[/math] on that cycle. By assumption, [math]\displaystyle{ (V,E_{i-1} \cup{\{e_i\}}) }[/math] is cycle-free as well. Therefore, [math]\displaystyle{ e }[/math] is none of the edges considered so far but one of [math]\displaystyle{ e_{i+1},...,e_{\vert E \vert } }[/math], which implies [math]\displaystyle{ \ell(e) \leq \ell(e_i) }[/math] and, hence, maximality of the spanning forest [math]\displaystyle{ F'_i := (V,E'_{i-1} \setminus \{e\} \cup{\{ e_i \}}) }[/math]. Clearly, this [math]\displaystyle{ F'_i }[/math] includes [math]\displaystyle{ F_i }[/math], so the second invariant is maintained again.

Complexity

Statement: The asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(n \cdot T(n) + m\cdot\log m ) }[/math] in the worst case, where [math]\displaystyle{ n = \vert V \vert }[/math] and [math]\displaystyle{ m = \vert E \vert }[/math], and [math]\displaystyle{ T(n) }[/math] is the complexity of a single unite operation.

Proof: The summand [math]\displaystyle{ \mathcal{O}(m\cdot \log m) }[/math] results from sorting all edges in the preprocessing. The main loop has [math]\displaystyle{ m }[/math] iteration. There are [math]\displaystyle{ n-1 }[/math] unite operations.