Самый простой способ создать список смежности неориентированного графа?

Question

Самое близкое, что я смог найти, это: https://csacademy.com/app/graph_editor/

Но он не генерирует график случайным образом. Я ищу, чтобы создать список смежности для графа узлов 1000+.

Пример. {0, 2, 3}, {1, 5}, ...

• Где узел 0 имеет ребра 0, 2, 3
• Узел 1 имеет ребра 1,5
• И так далее ...

Буду признателен за любую помощь.

Answer 1

Существует различных моделей для генерации случайных графов с определенными статистическими свойствами. В комментариях вы сказали, что распределение на самом деле не имеет значения для вашего варианта использования, поэтому простой моделью для использования является та, которая включает каждое потенциальное ребро с некоторой фиксированной вероятностью, независимо от того, включены ли другие ребра. Это распределение обычно называется G(n, p), где n - количество узлов, а p - вероятность включения ребра.

Алгоритм генерации графа из G(n, p) прост:

• Инициализация графа с n узлами и без ребер.
• Для каждой (неупорядоченной / упорядоченной) пары узлов u, v:
  • Генерация случайного действительного числа в диапазоне [0, 1].
  • Если это число меньше p, добавьте ребро u-v к графику.

Выбор между неупорядоченными парами и упорядоченными парами зависит от того, требуется ли вам неориентированный или ориентированный граф соответственно.

Поскольку требуется список смежности, на этапе инициализации будет создан список. содержит n пустых списков, и шаг «Добавить ребро» добавит v к u (и u к v списку, если график должен быть ненаправленным).

Вот пример реализации в Python:

from random import random
from itertools import product, combinations

def random_graph(n, p, *, directed=False):
    nodes = range(n)
    adj_list = [[] for i in nodes]
    possible_edges = product(nodes, repeat=2) if directed else combinations(nodes, 2)
    for u, v in possible_edges:
        if random() < p:
            adj_list[u].append(v)
            if not directed:
                adj_list[v].append(u)
    return adj_list

Примеры:

>>> random_graph(4, 0.5)
[[1, 2, 3],
 [0, 3],
 [0],
 [0, 1]]
>>> random_graph(5, 0.25, directed=True)
[[0, 2, 4],
 [1, 4],
 [0, 1, 2, 3],
 [1],
 [1, 2]]

Answer 2

Если вы хотите сгенерировать случайный граф с N узлами и M ребрами, самый простой способ - следующий алгоритм:

Пусть list будет списком всех пар (0, 1), ...., (0, N-1), (1, 2), ...., (N-2, N-1): все S = (N - 1) * N / 2 возможных ребер. Затем вам нужно сгенерировать случайное подмножество этого списка с размером M.

• Создать случайное число x0 от 0 до S-1
• Поменять элементы для индексов x0 и S-1
• Генерация случайного числа x1 от 0 до S-2
• Замена элементов на индексы x1 и S-2
• (повторяйте до тех пор, пока вы не сгенерируете M числа)

Последние M элементы в списке образуют случайное подмножество ребер. Затем вы можете просто добавить их в свой график и создать списки смежности, как хотите.