我有一个顶点列表，我必须从中选择一个概率与 deg(v) 成比例的随机顶点，其中 deg(v) 是顶点度数。此操作的伪代码如下所示：
Select u ∈ L with probability deg(u) / Sigma ∀v∈L deg(v)
其中 u 是随机选择的顶点，L 是顶点列表，v 是 L 中的一个顶点。问题是我不明白该怎么做。有人可以向我解释一下，如何获得这个随机顶点。如果有人可以向我解释这一点，我将不胜感激。伪代码将更加感激；）。
问问题
760 次
2 回答
3
Sum(d(v))最简单的解决方案是为每个填充一个 size 列表v- 您将v在列表的确切 d(v)条目中保存一个引用。
x现在，在 range 中选择一个均匀分布的变量[0,Sum(d(v)))，然后返回list[x]
这种方法需要O(n^2)空间（因为对于简单的图Sigma(d(v)) is O(n^2)），初始化时间也是O(n^2)，但只进行一次。假设您要多次选择一个顶点，每次选择它时，除了第一次之外，将是O(1)[假设O(1)随机化函数和随机访问列表]。
于 2012-07-18T12:55:30.840 回答
3
另一种解决方案；仍然很简单，不需要任何预处理或额外内存（如果您在图中有边列表）：
选择一条随机边，然后随机选择它连接的节点之一；那是你的随机顶点。概率与顶点度成正比 - 对于每个节点，概率为
P(v) = sum(P(e: e uses v))/2 = |{e: e uses v}|/(2*|E|) = deg(v)/(2*|E|)
于 2012-07-18T16:19:07.140 回答