I want to randomly generate trees, i.e. undirected acyclic graphs with a single root, making sure that all possible trees with a fixed number of nodes n are equally likely.
How can I randomly generate trees?
11
$\begingroup$
probability-theory
random
2 Answers
1
To generate a random tree you can use the following algorithm, where dst
and src
are two stacks:
dst := random permutation of all nodes;
src := empty stack
src.push(dst.pop()); % picks the root
while (!dst.empty()) {
a := random element from src;
b := dst.pop();
add the edge (a, b)
src.push(b);
}
Proof of correctness (all trees are possible and equally likely): Alexey S. Rodionov and Hyunseung Choo, On Generating Random Network Structures: Trees, ICCS 2003, LNCS 2658, pp. 879-887, 2003.
4
Knuth says to look at it as generating all nested parentheses in lexicographic order.
Look here for the details
-
0Eric Lippert has been doing a series on something similar - http://blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx, which might be an interesting read. – 2010-07-26
-
0I only read the first few sentences but its interesting that binary tree's are Catalan numbers, I knew triangulations were, but either learned that and forgot or never knew. – 2010-07-26
-
0Thanks for the references, but both of them seem to be generating *all* trees, I just want to generate a single tree at random, but making sure all of them are equally likely. Also, it would be nice to post here the actual answers, and not pointers to external documents which might become broken links in the future. – 2010-07-26
-
0Link to obsolete url? – 2018-03-28