Проверьте, имеет ли изменяющийся неориентированный граф хотя бы один круг

Question

У меня есть неориентированный граф, который изначально не имеет ребер. Теперь на каждом шаге добавляется или удаляется край, и нужно проверить, имеет ли граф хотя бы один круг. Вероятно, самым простым достаточным условием для этого является

подключенные компоненты + количество ребер < = количество узлов.

Поскольку «шаги», упомянутые выше, выполняются миллионы раз, эта проверка должна быть действительно быстрой. Поэтому я задаюсь вопросом, что было бы быстрым способом проверить условие в зависимости от того, что на каждом шаге изменяется только один край.

Любые предложения?

Answer 1

Если вы знаете, какие два узла связаны новым краем, вы можете использовать какой-то алгоритм поиска путей для обнаружения альтернативного пути между двумя узлами. Другими словами, если существует путь, который соединяет два узла вашего нового края перед добавлением нового края, добавление нового ребра создаст круг.

Ваша задача сводится к finding the paths between two given nodes.

Answer 2

Я предлагаю вам маркировать все узлы. Используйте целые числа, это проще всего.

В любой момент ваш график будет разделен на несколько непересекающихся подграфов. Первоначально каждый узел находится в собственном подграфе.

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

Если и только если новый край соединит два узла с одинаковыми метками, то край будет создавать цикл.

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

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

Answer 3

Если вы увлечены, вы можете попытаться реализовать структуру данных динамического динамического соединения, как описано в "Poly-logarithmic deterministic fully-dynamic graph algorithms I: connectivity and minimum spanning tree" by Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup.

При добавлении ребра вы проверяете, подключены ли две конечные точки. Если нет, количество подключенных компонентов уменьшается на единицу. После удаления ребра проверьте, подключены ли две конечные точки. Если нет, количество подключенных компонентов увеличивается на единицу. Амортизированное время выполнения вставки и удаления краев будет O(log^2 n), но я могу представить, что постоянный коэффициент довольно высок.

Есть newer result с лучшими границами. Существует также experimental evaluation некоторых динамических алгоритмов связи, которые также рассматривают детали реализации. Существует также Javascript implementation. Я понятия не имею, насколько это хорошо.

Наверное, на практике у вас может быть намного легче, поддерживая остовный лес. Вы получаете бесплатную добавку к краю и удаление ненужных ребер (почти).Для удаления ребер на дереве вы можете просто использовать «грубую силу» в форме BFS или DFS, чтобы проверить, все ли подключены конечные точки. Особенно, если количество узлов ограничено, возможно, это на практике работает достаточно хорошо, BFS и DFS равны O(n^2) для плотных графов, и вы можете поручить часть этой работы тем операциям, в которых вам повезло, и им нечего было сделать ,