Лучший способ проверить полную достижимость

Question

У меня есть набор узлов, каждый из которых подключен хотя бы к одному другому узлу.Я хотел бы знать, таковы ли соединения, что каждый узел доступен из любого другого.Например:

1--2
   |
3--4

Против:

1--2

3--4

Я убежден, что такого рода тестирование достижимости можно спроецировать с точки зрения точная проблема с обложкой, однако я не могу понять, как это сделать.Есть ли у кого-нибудь указатели, документация, веб-сайты и т. д. о том, как это сделать?Примеры были бы чрезвычайно ценны.

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

Answer 1

• начните с любого узла и выполните обход в глубину/ширину
• подсчитать количество посещенных узлов (конечно, не посещайте ни один узел дважды!)
• сравнить подсчитанное число с общим числом

Answer 2

Существует также быстрый (но довольно сложный) алгоритм динамического поддержания связности (т.е.под вставками/удалениями ребер), показано в этой статье: Полилогарифмические детерминированные полностью динамические алгоритмы связности, минимального остовного дерева, 2-ребер и двусвязности.

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