随机简单连通图生成与给定稀疏 [英] Random simple connected graph generation with given sparseness

问题描述

我试图找到一个高效的算法来生成与给定的稀疏一个简单的连通图。是这样的：

 输入：
    N  - 生成的图形的大小
    的S  - 稀疏（边缘NUMER实际上;从N-1到N（N-1）/ 2）
输出：
    简单连通图G（V，E）有n个顶点和S边
 

解决方案

对于每个节点至少需要一个边缘。

开始一个节点。 在每次迭代中，创建新的节点和一个新的边缘。边缘是从previous节点集中的随机节点连接新节点。

创建了所有节点

后，创建随机的边缘，直到S被满足。确保不要产生双重边缘（对于这一点，你可以用一个邻接矩阵）。

随机图是O（S）完成。

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.

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

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