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)
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.
To generate the random permutation see Fisher-Yates shuffle, e.g. Recipe 4.17 in the Perl Cookbook.
