Random simple connected graph generation with given sparseness
algorithm, graph, random
Solution
For each node you need at least one edge.
Start with one node. In each iteration, create a new node and a new edge. The edge is to connect the new node with a random node from the previous node set.
After all nodes are created, create random edges until S is fulfilled. Make sure not to create double edges (for this you can use an adjacency matrix).
Random graph is done in O(S).
Problem
I'm trying to find an efficient algorithm to generate a simple connected graph with given sparseness. Something like: ``` Input: N - size of generated graph S - sparseness (numer of edges actually; from N-1 to N(N-1)/2) Output: simple connected graph G(v,e) with N vertices and S edges ```