Kruskal’s Algorithm
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 ...
Get Mazes for Programmers now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
