128 CHAPTER 2 Discrete Mathematics
Kruskal’s algorithm
Kruskal’s algorithm is the same in spirit as the Cheapest-Link
algorithm for finding minimal-weight Hamiltonian cycles. However,
the surprising difference is that whereas the Cheapest Link algorithm
doesn’t always find the minimal-weight Hamiltonian cycle, Kruskal’s al-
gorithm will always find the minimal-weight spanning tree in a weighted
graph.
The algorithm is implemented by selecting in turn the edges of min-
imal weight—and hence is a greedy algorithm—disregarding any choice
that creates a circuit in the graph. The algorithm ends when a spanning
tree is obtained.
We indicate in steps how
the minimal-weight span-
ning tree for the exam-
ple on page 127 was ob-
tained (notice that we
couldn’t choose the edge
with weight 2.5, as this
would create a cycle: