### zeldris's blog

By zeldris, history, 6 months ago, ,

Hello,

I need to build a connected graph with 1e5 vertices and 4e5 edges, but when I try to create using rand () I can not get such a graph. can anybody help me?

P.S. the edges must be different.

•
• +5
•

 » 6 months ago, # |   +11 Maybe you can build a tree first: for i=2 to n link(i,rand()%(i-1)+1) (1-index) and then use another permutation of [1,n] to replace the original index.After building the tree,add some arbitary edges. if you do not want to get repeated edges,use hash or map to check.
•  » » 6 months ago, # ^ | ← Rev. 4 →   +5 Getting all graphs with the same probability (that is, getting the uniform distribution) could be desirable. I guess you can use Prüfer codes if you just want a random tree on n vertices. Even in this case, Wilson's algorithm for generating a spanning tree of a graph G uniformly at random is reasonably efficient.Example: What should be the probability of getting a 4-vertex star (that is, a tree with 3 leaves and a vertex of degree 3)? There are nn - 2 labeled trees (Cayley), and n of those are stars because you can only choose the central vertex, so for n = 4 the correct probability is 4 / 44 - 2 = 1 / 4.
•  » » 6 months ago, # ^ |   +5 thanks
 » 6 months ago, # |   +8 By the way, there exists extrimely convinient library jngen for these needs and similar.
•  » » 6 months ago, # ^ |   +13 SPOJ also has a useful test case generator.