頂点のリストがあり、そこから deg(v) に比例する確率でランダムな頂点を選択する必要があります。ここで、deg(v) は頂点の次数です。この操作の擬似コードは次のようになります。
Select u ∈ L with probability deg(u) / Sigma ∀v∈L deg(v)
ここで、u はランダムに選択された頂点、L は頂点のリスト、v は L 内の頂点です。問題は、その方法がわからないことです。このランダムな頂点を取得する方法を誰かに説明してもらえますか? 誰かが私にこれを説明していただければ幸いです。擬似コードはさらに高く評価されます;)。
最も簡単な解決策は、サイズのリストをSum(d(v))それぞれに入力することです。リストの正確なエントリにvへの参照を保持します。v d(v)
xここで、範囲内の一様分布変数を選択して[0,Sum(d(v)))、list[x]
この方法はO(n^2)（単純なグラフの場合からSigma(d(v)) is O(n^2)）スペースを必要とし、初期化時間もO(n^2)ですが、これは1回だけ実行されます。頂点を何度も選択すると仮定すると、最初の頂点を除いて、頂点を選択するたびに、 [ランダム化関数とランダムアクセスリストをO(1)想定]になります。O(1)
別の解決策。まだシンプルで、前処理や追加のメモリは必要ありません (グラフにエッジのリストがある場合):
ランダムなエッジを選択し、それが接続するノードの 1 つをランダムに選択します。それがあなたのランダムな頂点です。確率は頂点の次数に比例します。すべてのノードの確率は
P(v) = sum(P(e: e uses v))/2 = |{e: e uses v}|/(2*|E|) = deg(v)/(2*|E|)