Соединение двух случайных узлов в ориентированном ациклическом взвешенном графе

Question

Сводка

Итак, у меня есть ориентированный ациклический взвешенный граф, где у каждого ребра есть входной и выходной узлы, у каждого узла есть идентификатор, и я использую словарь, чтобы отобразить все входящие ребра водин узел по его идентификатору, а другой - для всех исходящих ребер, поэтому при представлении идентификатора узла я могу сообщить всем входящим и исходящим ребрам за ~ O (1) время.

Требование

Мне нужно иметь возможность добавлять новые случайные ребра (т.е. соединять два случайных узла) таким образом, чтобы гарантировать, что независимо от того, насколько велик граф, он не будет иметь циклов.

Что я пытался

Так как я полностью контролирую, как построить свой граф, я мог бы отсортировать его топологически и использовать алгоритм Кана для расчета, если для двух равномерно случайно выбранных узлов N1 и N2график приведет к циклу за время O (n).Проблема в том, что если это произойдет?Мне придется попробовать новую случайную пару и повторять процесс, пока мне не повезет.Звучит так, как будто он будет очень плохо масштабироваться с графиком, поскольку чем плотнее ребро на графике, тем больше вероятность того, что новый случайный объект создаст цикл.

Я также читал этот пост: Генерация случайной группы доступности базы данных , которая по своей природе аналогична моей проблеме, однако я не могу использовать предлагаемое решение для подключения узлов на основе их идентификаторов и подключать только меньшие к большим идентификаторам (узлы, которые были ранее с узлами, которыеновые) из-за других ограничений, которые у меня есть на проблему.

Вопрос

Есть ли способ спроектировать структуру, которая позволит мне только случайным образом выбратьмежду узлами, ни один из которых, если он подключен через новое ребро, не приведет к циклу, не зависящему от затрат памяти?Тогда это должна быть операция O (1).

Answer 1

У меня есть решение O (1) для проверки возможности включения ребра в график. Однако вам понадобится худший случай O (n) , чтобы вставить ребро.

Вы можете сохранить двоичную матрицу достижимости R, где R[u, v]=1, если вы можете достичь v с u в вашем текущем графике и R[u, v]=0, если нет. R можно вычислить один раз, используя Флойд-Варшалл .

Если вы хотите проверить, можете ли вы включить ребро (u,v), вам просто нужно проверить, если R[v, u] = 0. Если это R[v, u] = 1, вы строите круг, вставляя (u,v).

Остальной проблемой становится обновление этой структуры. Если в итоге вы вставите ребро (u, v) в график, вы установите R[u, v] = 1. Кроме того, все узлы, которые смогли достичь u (R[:,u]=1), теперь могут достигать всех узлов, достижимых на v (R[v,:] = 1). Таким образом, вам нужно будет установить свои записи R[i, j] = 1, если R[i,u] = 1 и R[v:j] = 1.

К сожалению, шаг обновления примет O (n) в худшем случае

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