隨機數發生器和圖算法

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，那麼它位於第二個區間，所以選擇第二個邊。