The two hemispheresI due emisferi
The northern hemisphere (left) and the southern one (right) seen from outside, each mapped so that distances from its pole are kept; the start in gold, the goal in dark. With frequency f the icosahedron has each face cut into f² triangles, which gives 10f² + 2 cells.
L'emisfero nord (a sinistra) e quello sud (a destra) visti da fuori, ciascuno mappato in modo da conservare le distanze dal suo polo; la partenza in oro, l'arrivo in scuro. Con frequenza f l'icosaedro ha ogni faccia tagliata in f² triangoli, il che dà 10f² + 2 celle.
Wilson's algorithm grows the tree from one cell: from each cell not yet in the tree it walks at random until it hits the tree, erasing every loop the walk closes, and adds the path that remains. The result is a uniform spanning tree, each of the (very many) spanning trees with the same probability, which a depth-first search would not give, since it favors long corridors with few branches.
L'algoritmo di Wilson fa crescere l'albero da una cella: da ogni cella non ancora nell'albero cammina a caso finché non lo tocca, cancellando ogni ciclo che il cammino chiude, e aggiunge il percorso che resta. Il risultato è un albero ricoprente uniforme, ciascuno dei (moltissimi) alberi ricoprenti con la stessa probabilità, cosa che una visita in profondità non darebbe, perché favorisce corridoi lunghi con pochi rami.