Michael Bradford Williams

Home / Programming / Random Paths in a Graph

The goal with this program is to totally cover the vertices of a graph with random, non-self-intersecting paths. The procedure to create a path is to choose an unvisited vertex randomly, move along an edge to a random unvisited neighboring vertex, and repeat until the path cannot be extended any further. Paths are created in this way until all vertices of the graph have been visited.

The process is animated below, and there are a few types of graphs to choose from: rectangular, triangular, or hexagonal grids.

Here is a larger version of this program that is more suited to desktop browsers.

Graph:  

Your browser is currently unsupported.