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
-
0Link to obsolete url? – 2018-03-28