Как мне сделать функцию, которая принимает numVertices и numEdges, а затем ВСЕГДА генерирует связанный граф?

Question

• Я хочу создать связанный, ненаправленный граф, который содержит n вершин и m ребер. В частности, я хочу сгенерировать граф с узлами, которые содержат ровно одно целое число от 0 до n - 1.

• Я посмотрел несколько глубоко на этом сайте и мог не найти то, что я искал. Я буду признателен за любую предложенную помощь. Спасибо!

Answer 1

Я не знаю о существующих библиотеках, но это решение с нуля. Предположим, у вас есть n узлов и m ребер. Для генерации простого (без дублирующего ребра) связного графа m, n должно удовлетворять этому условию:

n - 1 <= m <= n * (n - 1) / 2

Процесс (узлы индексируются от 0 до n - 1):

1. Создайте связующее дерево, чтобы убедиться, что граф подключен. Есть много способов (например, последовательность Prufer), но вот простой способ:

for i = 1 to n - 1: add_edge(i, randint(0, i - 1))

Чтобы сделать его более случайным, вы можете перетасовать порядок сначала узлы.

Добавляйте больше ребер, пока не получите m ребер.

while there are less than m edges: a, b = randint(0, n - 1), randint(0, n - 1) if (a != b and edge(a, b) has not existed): add_edge(a, b)

Примечание: randint(a, b) = случайное целое число в диапазоне [a, b].

Коды выглядят простыми, но на практике работают очень быстро. Вы можете рассчитать ожидаемое количество итераций, чтобы понять, почему.