Three simple algorithms that efficiently finds the Minimum Spanning Tree:
Implementation from our class' lecture:
for each (v ∈ V) a[v] = ∞
Initialize an empty priority queue Q
for each (v ∈ V) insert v onto Q
Initialize set of explored nodes S = φ
while (Q is not empty)u = delete min element from Q
S = S ∪ { u }
for each (edge e = (u, v) incident to u)if (v ∉ S) and (ce < a[v])decrease priority a[v] to ce
There are several applications of the Minimum Spanning Tree algorithms, many can be found in the book.
This was by far the most interesting reading of the chapter!I give it a 9/10.