O'Reilly logo

Mazes for Programmers by Jamis Buck

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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.

images/connected-grid.png

Merely constructing ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required