11
$\begingroup$

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.

2 Answers 2

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

http://www-cs-faculty.stanford.edu/~uno/fasc4a.ps.

  • 0
    Link to obsolete url?2018-03-28