Лучший способ проверить полную достижимость
-
19-09-2019 - |
Вопрос
У меня есть набор узлов, каждый из которых подключен хотя бы к одному другому узлу.Я хотел бы знать, таковы ли соединения, что каждый узел доступен из любого другого.Например:
1--2
|
3--4
Против:
1--2
3--4
Я убежден, что такого рода тестирование достижимости можно спроецировать с точки зрения точная проблема с обложкой, однако я не могу понять, как это сделать.Есть ли у кого-нибудь указатели, документация, веб-сайты и т. д. о том, как это сделать?Примеры были бы чрезвычайно ценны.
Обновлять: Меня выдало мое невежество, поскольку, казалось бы, существуют гораздо более эффективные алгоритмы для такого рода тестов.Если у вас есть такой, пожалуйста, укажите мне на него.
Решение
- начните с любого узла и выполните обход в глубину/ширину
- подсчитать количество посещенных узлов (конечно, не посещайте ни один узел дважды!)
- сравнить подсчитанное число с общим числом
Другие советы
Существует также быстрый (но довольно сложный) алгоритм динамического поддержания связности (т.е.под вставками/удалениями ребер), показано в этой статье: Полилогарифмические детерминированные полностью динамические алгоритмы связности, минимального остовного дерева, 2-ребер и двусвязности.
Основная идея — поддержка связующего дерева.Простыми случаями являются вставка ребра и удаление ребра, не являющегося связующим деревом.Проблема заключается в удалении ребра связующего дерева, потому что теперь нет гарантированной связности — нам приходится эффективно искать альтернативный маршрут для соединения сломанных частей, иначе граф будет отключен.