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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Knuth says to look at it as generating all nested parentheses in lexicographic order.
Look here for the details
To generate a random tree you can use the following algorithm, where
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.