Алгоритм генератора и диаграмм случайных чисел

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, затем он находится в 2-м интервале, поэтому выберите 2-й край.