= Aldous-Broder algorithm
{c}
{wiki}
The <Aldous-Broder algorithm> samples a <uniform spanning tree> of a finite <connected graph> by running a simple <random walk> from any initial <vertex>. Whenever the <random walk> first visits a new <vertex>, retain the <edge> by which it arrived. Stop when every <vertex> has been visited.
Each retained <edge> joins a previously unseen <vertex> to the already visited <connected> <subgraph>. It cannot create a <graph cycle>; at termination the retained <edges> form a <spanning tree>. The stopping time is the <cover time>, finite <almost surely>. The nontrivial conclusion is that every <spanning tree> has exactly the same <probability>, independently of the starting <vertex>.<The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees by David Aldous>[section1, equation1 and Proposition1]{ref}
Repeated visits add no <edges>, which can make the method slow when only a few unvisited <vertices> remain. <Wilson's algorithm> instead attaches <loop-erased random walks>. On a recurrent infinite <connected graph>, the first-entrance construction continues indefinitely and gives the corresponding infinite-volume <uniform spanning tree>.
Back to article page
