Let G = (V, E) be a connected graph and c : E → R be a cost function on its edges such that different edges have different costs.
T ← (V, ∅);
while (T is unconnected) do
let T1, T2, . . . Tp be the connected components of T; // p > 2
for (i = 1, p) do
let ei ∈ E such that c(ei) = min {c(uv) : uv ∈ E, u ∈ V (Ti), v /∈ V (Ti)};
E(T) ← E(T) ∪ {e1, e2, . . . , ep};
return T;
Prove that
(a) after each while iteration the number of connected components of T is at least halved;
(d) the number of the while iterations is O(log n) and each while iteration takes O(m) time, hence the overall time complexity of the above algorithm is O(m log n). ( n = |V |, m = |E|)
(b) does not necessarily hold. Suppose we have T with 3 components T1, T2 and T3. We could pick edges e1 connecting T1 to T2 and e2 connecting T2 to T1 with e1 not equal to e2. Adding e1, e2 to T will result in a graph with a cycle. The standard algorithm (Kruskal's) only adds one edge at a time, and this is partly why.
To answer your questions, you might be interested in looking into Borůvka's algorithm dated back to 1926. In the literature, you can also find it under the name of Sollin's algorithm. A good starting point might be Chapter 13 of "Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. 1993. Network flows: theory, algorithms, and applications. Prentice-Hall, Inc., USA.", where you can find a comprehensible explanation.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs