Kruskal's algorithm
- Produces minimum spanning tree, MST (aka minimum connector).
- An MST is such that the total length of its arcs is as small as possible.
- Kruskal's algorithm:
- Sort all the arcs into ascending order of weight.
- Select the arc of least weight to start the tree.
- Consider the next arc of least weight. If their is a choice of equal arcs, consider each in turn.
- If it would form a cycle with the arcs already selected, reject it.
- If it does not form a cycle, add it to the tree.
- Repeat step 3 until all vertices are connected