0

マルチグラフ（加重グラフ）からの重みに応じて、均一なエッジでランダムに選択したいと思います。Kargers algo で説明されているように、これを作成したいと思います。

アルゴには次の 2 つの部分があります。

これはランダム選択方式です。

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[][] 行列です。

そして、各頂点の行の累積合計を持つ配列があります。

しかし、これを自分のコードに正しく実装する方法がわかりません。

誰か助けてくれませんか？

ありがとうございました。

4

1 に答える 1

0

メソッドは次のとおりです。

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

わからない場合は教えてください。コメントを追加します。

于 2013-04-29T15:37:51.763 に答える