View source for Kruskal for maximum spanning forest

[[Category:Videos]]
{{#ev:youtube|https://www.youtube.com/watch?v=Pz6x3BB86YA|500|right|Chapters
#[00:00] Einführung
#[01:59] Der Algorithmus von Kruskal anhand eines Beispiels
#[06:56] Und wie ist das bei mehreren Zusammenhangskomponenten?
#[07:29] Welches Problem löst der Algorithmus von Kruskal genau?
#[08:05] Wie lautet die Invariante?
#[08:33] Warum ist der Algorithmus korrekt?
#[08:59] Wie wird die Invariante sichergestellt?
#[10:25] Was ist die asymptotische Komplexität des Algorithmus?
|frame}}
'''Algorithmic problem:''' [[Maximum spanning forest]]

'''Prerequisites:'''

'''Type of algorithm:''' loop

'''Auxiliary data:'''

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

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

'''Variant:'''  <math>i</math> increases by <math>1</math>.

'''Break condition:'''  <math>i = \vert E \vert</math>.

==Induction basis==
'''Abstract view:'''
# <math>E_0 := \emptyset</math>
# <math>U F</math> is initialized by <math>V</math>, so each node <math>v \in V</math> is a singleton in <math>U F</math>.
'''Implementation:''' Obvious.

'''Proof:''' Nothing to show.

==Induction step==
'''Abstract view:''' If inserting <math>e_i</math> would close a cycle, reject <math>e_i</math>; otherwise, insert <math>e_i</math>.

'''Implementation:'''
#Let <math>v,w \in V</math> denote the endnodes of <math>e_i</math>, that is, <math>e_i = \{v,w\}</math>.
#If <math>v</math> and <math>w</math> belong to different sets in <math>U F</math>:
##Insert <math>e_i</math> in the result.
##Unite the sets of <math>v</math> and <math>w</math> in <math>U F</math>.

'''Correctness:''' The first and third invariants are obvious. So we focus on the second invariant. We may safely set <math>F'_i := F'_{i-1}</math> if
#either <math>e_i \in E'_{i-1}</math> and <math>e_i</math> is inserted in the <math>i</math>-th iteration
#or <math>e_i \notin E'_{i-1}</math> and <math>e_i</math> is rejected in the -th iteration.
Note that the case that <math>e_i \in E'_{i-1}</math> and <math>e_i</math> is rejected cannot occur. In fact, <math>e_i \in E'_{i-1}</math> implies that <math>(V,E_{i-1} \cup{\{e_i\}})</math> is cycle-free, but rejecting <math>e_i</math> implies that <math>(V,E_{i-1} \cup{\{e_i\}})</math> contains a cycle. So it remains to consider the case that <math>e_i</math> is accepted but <math>e_i \notin E'_{i-1}</math>.
 
As <math>\ell(e_i) > 0</math> and <math>F'_{i-1}</math> is maximal, <math>(V,E'_{i-1} \cup{\{e_i\}})</math> contains a cycle. Since <math>F_{i-1}</math> is cycle-free, there must be an edge <math>e \in E'_{i-1} \setminus E_{i-1}</math> on that cycle. By assumption, <math>(V,E_{i-1} \cup{\{e_i\}})</math> is cycle-free as well. Therefore, <math>e</math> is none of the edges considered so far but one of <math>e_{i+1},...,e_{\vert E \vert }</math>, which implies  <math>\ell(e) \leq \ell(e_i)</math> and, hence, maximality of the spanning forest <math>F'_i := (V,E'_{i-1} \setminus \{e\} \cup{\{ e_i \}})</math>. Clearly, this <math>F'_i</math> includes <math>F_i</math>, so the second invariant is maintained again.

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

'''Proof:''' The summand <math>\mathcal{O}(m\cdot log\cdot m)</math> results from sorting all edges in the preprocessing. The main loop has <math>m</math> iterations, and each iteration takes <math>\mathcal{O}(T(n))</math> time.