The mini javascript projects continue apace. Today’s little program: an implementation of Wilson’s Algorithm.
In graph theory a spanning tree is a set of edges in a graph such that all vertices are included but no loops are formed. More formally, “a spanning tree T of a connected, undirected graph G is a tree that includes all of the vertices and some or all of the edges of G.”
Spanning trees have a number of practical uses, one of the most important being to allow loop-free communication within a computer network using the Spanning Tree Protocol.
Wilson’s Algorithm is a method of creating a random spanning tree (technically a uniform spanning tree) in an arbitrary graph using a loop-erased random walk. A loop-erased random walk is formed as follows:
- Chose a starting point to form the start of your path
- For the node at the end of the path, add a neighbour at random
- If that node is already on the path, remove the loop it would have formed
- If not on the path, add it to the end
- Repeat until some end-condition is reached
To use this process to create a whole tree:
- Choose a random starting point
- Perform a loop-erased random walk from this point until your path is a certain length, or for an arbitrary number of iterations.
- This path forms the start of your tree
- Chose a random point not already on the tree and perform a loop-erased random walk until it touches the tree
- Repeat #4 until all nodes are added to the tree
For a graph of any non-trivial dimensions it is obvious that in the beginning it will take a frustrating amount of time for the random walk to join the tree, but as time goes by and the three occupies more nodes and – more importantly – spreads across the graph paths are more and more likely to join more quickly. The process accelerates until all nodes are on your tree.
Once the tree is finished we can perform a neat little finishing flourish by flood-filling from the root of the three, letting you see the actual structure of it.