|
|
Find the set of edges connecting all nodes such that the
sum of the edge length is minimized
GREEDY ALGORITHM FOR MST
Initial
Select any node arbitrarily and let this node alone form the
set S1. Put all other nodes in the set S2.
Selection
From all the edges with one end in the set S1 and the other
end in the set S2, select the one with the smallest length.
Let this edge be (i, j).
Add this edge to the spanning tree. Add node j to the set S1
and delete it from the set S2.
Finish
If the set S1 includes all the nodes, stop with the minimum
spanning tree. Otherwise repeat the Selection step.
|
Click on the nodes in the order that they should be added to
the tree. |
