我正在尝试寻找一种有效的算法来生成具有给定节点数的简单连通图。像这样的东西:
Input:
N - size of generated graph
Output:
simple connected graph G(v,e) with N vertices and S edges, The number of edges should be uniform distribution.
最佳答案
您可能想先创建一个最小生成树以确保连通性。稍后，随机生成两个节点(尚未连接)并将它们连接起来。重复直到你有 S 边。
对于最小生成树，最简单的做法是从一个随机节点作为树开始。对于每个剩余节点(随机排序)，将其连接到树中的任何节点。您在树中选择(连接)节点的方式定义了边/节点的分布。
关于algorithm - 生成边分布均匀的随机图，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20184232/