Search code examples
algorithmrandomgraph

Random simple connected graph generation with given sparseness

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
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).