block by mbostock 949c772b81296f8e4188

Randomized Depth-First III

Full Screen

A spanning tree of the canvas is generated using randomized depth-first traversal and then flooded with color. Hue encodes Manhattan distance from the root of the tree. (This is not an optimal visual encoding, but it suffices and is pretty.)

Spanning trees can also be used to generate mazes. See a maze generated with randomized depth-first traversal flooded with color, and compare color floods of spanning trees generated by random traversal, Prim’s algorithm, and Wilson’s algorithm.