Q:

Given a simple graph G, what's the quickest known way to sample one of its spanning trees at random?

Let's say I have a simple graph G with an edge set E, vertex set V, and at least 1 cycle.
We can determine the number of spanning trees in this graph by finding its graph Laplacian matrix, striking out one row and column, and then taking the determinant of that sub-matrix.
Let's call that determinant t (i.e. there are t possible spanning trees in total).
What is the quickest known algorithm such that its input is G and it's output is one of t possible spanning trees of G (where each spanning tree has as close to $\frac{1}{t}$ chance of being selected as possible)?
Here's the algorithm I'm using currently.

Definitions:
$V_{visited}$ - vertices already traversed
$E_{visited}$ - edges already traversed
$V_C$ - V \ V_visited (i.e. vertices in V but not in $V_{visited}$)
N($V_{visited}$) - the set of all vertices v in $V_C$ such that an edge 
exists between v and some vertex in $V_{visited}$

Algorithm:

sample $v_0$ from V randomly
add $v_0$ to $V_{visited}$
sample $v_1$ from N($V_{visited}$) randomly
add ($v_0$, $v_1$) to $E_{visited}$
sample $v_2$ from N($V_{visited}$) randomly
add ($v_*$, $v_2$) to $E_{visited}$ (where $v_*$ is a randomly chosen from $v_2$'s neighbors in $V_{visited}$)

...

sample $v_{|V| - 1}$ (the second to last vertex in V) randomly
add ($v_*$, $v_{|V| - 1}$) to $E_{visited}$ (where $v_*$ is a randomly chosen from $v_{|V| - 1}$'s neighbors in $V_{visited}$)
sample $v_{|V|}$ (the last vertex in V)
add (v*, $v_{|V|}$) to $E_{visited}$ (where $v_*$ is a randomly chosen from $v_{|V|}$'s neighbors in $V_{visited}$) 

Now $V_{visited}$ and $E_{visited}$ represents a random spanning tree of G.

Is this the most efficient way of getting a random spanning tree? Is there a more efficient way? (Bonus points if it's parallelizable.)

A:

I recommend Wilson's Algorithm. It is proven to select spanning trees uniformly at random. In worst case scenarios it can have complexity $n^3$, but in practical usage it often runs much faster, I believe typically $n log(n)$. I am part of a large research project at Duke and this is the algorithm we use. The current algorithm you have while faster, does not accurately sample randomly, one simple counter-example would be a star graph with an extra edge.
At the start, you have one visited vertex, and one exploring vertex (both randomly chosen). You start a random walk from the exploring vertex, until you hit a visited vertex. When the random walk makes a loop, you delete the loop from your walk, and carry on. When you hit a visited vertex, you append the vertices of your current walk to the visited vertices, and save the edges of the walk to the tree you will return. Then, you choose a new exploring vertex, and do another random walk, repeating until all vertices are visited vertices.
Here's a paper on Wilson's Algorithm and it's predecessor, the Aldous-Broder Algorithm. (which is worse in practice usually)

