java - 用二分搜索均匀随机

Question

我想根据多重图（加权图）中的权重选择均匀边缘的随机值。我想让它像 Kargers 算法中描述的那样。

该算法有两个部分：

这是一种随机选择方法。

From edges e1...em with weights w1...wm construct cumulative weights 
Wk=sum(wi,from=i=1,to=k).
Then choose an integer r uniformly at random from 0...Wm and use binary search to
identify the edge ei such that Wi-1 <= r < Wi.

然后我们可以用这个方法找到一条随机边。

Goal is to choose an edge (u,v) with probability proportional to W(u,v).
First choose endpoint u with probability proportional to D(u) and then once u is
fixed choose a second endpoint v with probability proportional to W(u,v).

我已将图形实现为相邻矩阵。这看起来像这样。

       v1 v2 v3 v4
    v1 0  1  0  2
    v2 1  0  3  0
    v3 0  3  0  0
    v4 2  0  0  0

在我的代码中，矩阵是一个 int[][] 矩阵；

我有一个数组，其中包含每个顶点的行的累积总和。

但现在我不知道如何在我的代码中正确实现这一点。

有人可以帮我吗？

谢谢你。

Answer 1

继承人的方法：

public static int sumOfRow(int[][] array, int rowIndex) {
    int sum = 0;
    for(int i : array[rowIndex]) {
        sum += i;
    }
    return sum;
}

如果您不明白，请告诉我，我会添加一些评论。