随机简单连通图生成与给定稀疏 [英] 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屋!
查看全文