Привет, друзья!
Сегодня мы с вами не будем решать конкретную задачу, а познакомимся с новой структурой данных.
Представим, что перед нами есть карта, на которой схематично обозначены 8 городов. При этом, города 0, 1, 2 и 3 соединены между собой дорогами. Города 4, 5 и 6 также соединены между собой, а город 7 обособлен и не имеет сообщения с другими.
Таким образом города являются вершинами графов, а дороги — их ребрами.
Города могут иметь прямое соединение, как например 4 и 6, или же транзитивное как в случае 0 и 3. В результате мы имеем три непересекающихся множества:
— [0, 1, 2, 3]
— [4, 5, 6]
— [7]
Теперь нам нужно построить эффективную структуру, которая позволит быстро понимать, соединены ли два города между собой, и даст возможность объединять два непересекающихся множества в одно.
Для подобных задач можно использовать структуру данных Disjoint Set, которую также иногда называют Union Find.
Базовая реализация
Базово такая структура данных должна поддерживать три основных метода
find(x int) int
find — Находит рутовый элемент в множестве для указанного узла;
union(x int, y int)
union — Объединяет два множества путем соединения двух вершин в них между собой;
connected(x int, y int)
connected — Проверяет соединены ли две вершины графа между собой, то есть входят ли они в одно множество.
Внутри структура будет хранить связи между вершинами графа в виде массива, где индекс массива обозначает номер города, а значение по индексу — индекс рутового узла в графе.
- В первом множестве решим, что рутовым узлом будет город с номером 0. Он же является рутовым узлом для самого себя.
- Во втором множестве выберем город с номером 4. Он также является рутовым узлом для самого себя.
- Семерка ни с чем не связана, поэтому она является рутовым узлом в своем множестве.
Таким образом для нашего случая массив должен иметь следующий вид.
[0, 0 , 0, 0, 4, 4, 4, 7]
Поиск
Теперь не сложно догадаться, что для реализации поиска достаточно получить индекс рутового узла для конкретного города по его индексу в массиве.
Проверка связности
Проверка связности тоже реализуется крайне легко. Нужно получить рутовые элементы для города x и y при помощи метода find и сравнить их. Если два города имеют один и тот же рутовый город в графе, то они связаны либо напрямую, либо транзитивно.
Объединение множеств
Теперь предположим, что нам нужно соединить города с номерами 3 и 4, тем самым объединив первое и второе множества.
Мы решаем, что у объединенного множества родительский элемент остается равным 0. Это означает, что города с номерами 3, 4 и 5 должны получить связь с ним, то есть обновить значение своего рутового узла на 0.
Таким образом наш массив должен получить следующие значения.
[0, 0 , 0, 0, 0, 0, 0, 7]
Теперь осталось имплементировать структуру данных по описанной логике.
Подробную реализацию можно посмотреть в нашем блоге
#disjoint_set #graph