Generating Random Trees and Connected Graphs

16 May 2008

To generate a random (undirected) Connected Graph you first generate a spanning tree and then add additional edges at random.

To generate the random tree use the following algorithm

dst := random permutation of all nodes;
src.push(dst.pop()); % picks the root
while (!dst.empty()) {
  a := random element from src;
  b := dst.pop();
  add the edge (a, 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.

To generate the random permutation see Fisher-Yates shuffle, e.g. Recipe 4.17 in the Perl Cookbook.