I'm learning data structers and trying to write program, which would generate me a tree (not necessarily binary one) that contains n vertices. So far I tried Prufer sequence and it works for me well - it's very interesting solution of a problem. I found paper with Fast Random Tree Generating Algorithm (page 881-882).

Actually, I don't really care about speed of generation, but this method should be faster than generating tree from Prufer sequence. I wrote code to generate it, and I am not sure if it works correctly. Something is wrong with my code, or with the method presented in the above paper. Below I show what I produced. Code is written in Python3. Note that I changed indexing as Python is 0-indexed.

```
import random
def fast_random_tree(n):
"""
https://link.springer.com/content/pdf/10.1007/3-540-44862-4_95.pdf
"""
I = list(range(n)) # Initial vector of node numbers
root = random.randint(0, n - 2) # choosing root
I[root], I[-1] = I[-1], I[root] # replacing with last value
edges = [None for _ in range(n - 1)]
for m in range(n - 1):
t = random.randint(0, m) # new node
s = random.randint(m + 1, n - 1)
edges[m] = (I[t], I[s]) # adding edgde
I[t], I[n - m - 1] = I[n - m - 1], I[t] # replaceing from n-m+1 to n - nodes that are in a tree already
return edges
if __name__ == '__main__':
edges = fast_random_tree(5)
print(edges)
```

Sometimes I receive set of edges that does not create tree, because it contains cycles or graph is not fully connected. Example:

```
>>> print(fast_random_tree(5))
[(0, 4), (0, 3), (1, 2), (2, 1)]
0 1
/ \ |
4 3 2
```

which is obviously not a tree. What also concerns me is that root is choosen randomly and moved to last position in array, but it can never be connected to some other vertice.

Do I forget about something or just this algorithm does not work? If you know other algorithms to generate a random tree I would love to read about it. Thanks for any help in advance!