random - 随机数生成器和图算法

Question

G给定一种均匀随机选择 0 和 1 之间实数的方法，你将如何使用这个随机数生成器在有边的图中均匀随机选择一条n边。我知道您可以使用随机数生成器创建随机图G，但我很困惑如何修改它以在特定图中选择随机边G。

另一个问题浮现在脑海。鉴于该图G现在已加权，该算法将如何变化。我想现在权重会对选择的边缘产生更多影响，但它会改变算法多少

有什么见解吗？

Answer 1

对于未加权图，假设边存储在列表中，您可以简单地在1和之间生成一个统一的随机整数n。大多数库（在任何编程语言中）都会有一个介于 0 和 1 之间的统一随机数生成器u = U(0,1)。

现在将(0,1)区间统一划分为n子区间。对于“k”，范围从1 to n-1检查哪个间隔(k/n, (k+1)/n)确实u下降。k是你的随机优势。

对于加权图，如果目标是根据其权重随机选择一条边（权重越高意味着选择的可能性越大），则使用与上述相同的方法。但是(0,1)根据它们的权重将区间划分为子区间。最后生成u并选择k.

例如：如果有 3 条边的权重为 {1,2,3}。然后(0,1)按该比例将区间分成3个子区间。即(0,1/6)：(1/6,1/2)和(1/2,1)。生成u并找到它所在的区间。说u=0.45，那么它位于第二个区间，所以选择第二个边缘。