时间戳

首页 > 解决方案 > 以随机算法均匀生成具有 n 个顶点、m 个边的图

algorithm - 以随机算法均匀生成具有 n 个顶点、m 个边的图

问题描述

简单的问题，还没有找到简单的答案。我想要一个随机均匀的具有 N 个顶点、M 个边的图。在合理的时间复杂度内（我会说最坏的情况是准线性的）。这种算法是否存在，如果存在，它是什么？

编辑：澄清：该图是无向的，没有多边或循环边。

标签： algorithmrandomgraphprobability

解决方案

应该直截了当。只需生成N顶点。然后M是边缘。选择随机顶点作为源和目标。由于您没有其他要求（例如自动机语言），因此这是均匀分布的。

V <- {1, ..., N}
E <- {}
for 1 to M do
    edge <- (random(V), random(V))
    E.push(edge)
return (V, E)

编辑：澄清：该图是无向的，没有多边或循环。

继续生成随机边，直到你有一个有效的边：

V <- {1, ..., N}
E <- {}
for 1 to M do
    repeat
        source <- random(V)
        edge <- (source, random(V \ {source}))
    until E does not contain edge
    E.push(edge)
return (V, E)

用于目标random(V \ source)以排除循环。E does not contain edge不应该关心方向。即它应该考虑

(a, b) = (b, a)

为了提高效率，contains您应该在实现时使用一些散列结构。

问题是repeat循环。根据random工作的速度以及与可能的边缘数量的接近M程度，可能需要一段时间。您可以使用Floyd-Rivest 算法等技术加快此过程（另请参阅算法以选择单个随机值组合？）。

如果M与最大数量相比相当小，它应该运行得很快（在N和中线性M），因为您不会遇到很多边缘冲突。

推荐阅读