给定稀疏度的随机简单连通图生成

  • Z时代
  • 2024-01-10
  • 分类：问答

我试图找到一种有效的算法来生成具有给定稀疏性的简单连接图。就像是：

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

回答：

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

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

创建所有节点后，创建随机边，直到满足S。确保不创建双边缘（为此，您可以使用邻接矩阵）。

随机图以O（S）完成。

以上是 给定稀疏度的随机简单连通图生成 的全部内容， 来源链接： utcz.com/qa/417231.html

回到顶部