Kruskal’s algorithm was developed by the mathematician and computer scientist Joseph Kruskal in 1956 to construct what are called minimum spanning trees. Don’t be put off by the crazy vocabulary—spanning tree is really just a fancy name for these perfect mazes we’ve been generating, and minimum simply refers to the costs and weights we discussed in the previous chapter.

Basically, Kruskal was trying to solve the following problem. Let’s say you start with a graph, or grid, where every possible passage that might connect neighboring cells is given a cost. It might look something like the following figure.

Merely constructing ...

Start Free Trial

No credit card required