Использование структуры данных с несвязанными наборами может легко получить компонент связности Графа. И он просто поддерживает Инкрементные подключенные компоненты.
Однако в моем случае удаление края очень распространено, так что я ищу алгоритм, или новая структура может поддерживать Connected Components полностью динамически (включая добавление и удаление края)
Спасибо
Полилогарифмические детерминированные полностью динамические алгоритмы для связности, минимальное остовное дерево, 2-кратная и двухсвязная (Holm, de Lichtenberg and Thorup 2001) дает алгоритм, который позволяет произвольную последовательность запросов вставки, удаления и связности края, с обновлениями (вставками и удалениями) с учетом времени O (log (n) ^ 2) и запросов, принимающих O (log (n)/log (log (n))), причем n - число вершин в графе. Эти временные границы предполагают, что график начинается без краев.
Я только просматривал первые 2 из его 38 страниц, но не боюсь (тоже) боюсь - в документе описывается множество новых алгоритмов на динамических графах (то есть графики, которые могут быть эффективно изменены с течением времени) которая является самой простой.