Kruskal's Algorithm maze algorithm
Randomized Kruskal's algorithm shuffles every wall in the grid and removes each one that joins two separate regions.
How it works
Every cell starts as its own region. The algorithm goes through all the inner walls in random order. If the cells on either side of a wall belong to different regions, it removes the wall and merges the regions (with a union-find structure). If they're already connected, the wall stays, because removing it would create a loop.
Since walls are picked from anywhere in the grid, small passages appear all over at once and gradually join up. The finished maze has a lot of short dead ends, similar to Prim's, with no single direction of growth.
What to watch for
Watch little fragments of corridor appear scattered across the whole grid and then link together into one maze.
Properties
- Texture
- Short passages, many dead ends
- Dead ends
- Many
- Uniform
- No
- Speed
- Fast (near-linear with union-find)
- Memory
- One region label per cell
Try it
Open the studio to carve your own Kruskal's Algorithm maze at any size, solve it with up to four algorithms, and save the video. Or print one.
FAQ
Why doesn't Kruskal's algorithm make loops?
It only removes a wall when the two sides aren't connected yet, so it never creates a second path between two cells.
What does union-find do here?
It answers 'are these two cells already connected?' almost instantly, and merges two regions when a wall comes down.