随机数发生器和图算法

Question

给定一种随机统一选择0到1之间的实数的方法，你将如何使用这个随机数发生器来统一随机地选择一个边G和n边。 我知道你可以用随机数发生器创建一个随机图G，但我很困惑，因为如何修改它以在特定图G中选择一个随机边。

想到另一个问题。鉴于图G现在被加权，该算法将如何改变。我想现在权重会在选择的边缘上有更多的方位，但是它会改变算法的多少？

任何见解？

Answer 1

对于未加权曲线图，假定边缘存储在列表中，则可以简单地生成1和n之间的均匀的随机整数。大多数库（使用任何编程语言）将在0 之间具有统一的随机数生成器。

现在将(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，那么它位于第二个区间，所以选择第二个边。