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!