具有给定稀疏度的随机简单连通图生成 [英] 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

推荐答案

对于每个节点，您至少需要一条边.

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.

创建所有节点后，创建随机边，直到满足 S.确保不要创建双边(为此您可以使用邻接矩阵).

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

随机图是在 O(S) 中完成的.

Random graph is done in O(S).

这篇关于具有给定稀疏度的随机简单连通图生成的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！