I need to prove that the following algorithm produces a minimum spanning tree(MST) upon termination. I think, looking at the lecture notes, that I need to reduce the operations to red and blue rules (as e.g. explained here: )http://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/04mst.pdf
However, I think I don't even know where to start: In the beginning T is set to empty, so how can it even start as T doesn't even have any (connected) components?
Can someone explain how I'm supposed to interpret this algorithm and how I could show that it produces an MST?
Thanks in advance!
in: undirected graph G = (V, E), cost function c : E → R
out: minimum spanning tree T of G
1: T ← ∅
2: while T is not connected do
3: A ← ∅
4: for each connected component C of T do
5: let e be the cheapest edge in δ(C) (cut of C)
6: add e to A
7: end for
8: T ← T ∪ A
9: end while
It looks like Borůvka's algorithm (http://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm) and that T =(V,T) where the same name for graphs and edge sets is used.