G
给定一种均匀随机选择 0 和 1 之间实数的方法,你将如何使用这个随机数生成器在有边的图中均匀随机选择一条n
边。我知道您可以使用随机数生成器创建随机图G
,但我很困惑如何修改它以在特定图中选择随机边G
。
另一个问题浮现在脑海。鉴于该图G
现在已加权,该算法将如何变化。我想现在权重会对选择的边缘产生更多影响,但它会改变算法多少
有什么见解吗?
对于未加权图,假设边存储在列表中,您可以简单地在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
,那么它位于第二个区间,所以选择第二个边缘。