Использование массива вместо disjoint-set для алгоритма Крускала для более быстрого слияния и поиска

Question

так что только что узнал об алгоритме Крускала для минимальных остовных деревьев.Итак, вот мое понимание:

Инициализирует структуру данных с непересекающимся множеством, которая содержит все вершины V.

После сортировки ребер по весу в | E | log | E |время или | E |время с использованием счетной сортировки (если позволяют весовые коэффициенты), алгоритм Крукалса выполняет итерацию по отсортированным ребрам и добавляет ребро (u, v) к дереву минимального охвата, если узлы u и v не являются частью одного и того же набора в непересекающемся множествеСтруктура. Википедия говорит, что время поиска и поиска в этой структуре с непересекающимся множеством - это (V), где a - обратная функция Аккермана.

Я чувствую, что этот поиск может быть ускорен, но не уверен на 100% в сложности.Вот что я предлагаю:

Для каждой вершины графа присвойте ей значение от 0 до | V | -1, теперь эти числа являются их индексами.Инициализировать массив размером | V |со всеми значениями, установленными на 0.

При переборе наших ребер (u, v) мы можем искать их индексы за O (1) раз в массиве, если любое из этих значений массива равно 0, тогда мыустановите их в 1 и добавьте это ребро к нашему минимальному остовному дереву.

Такое ощущение, что мы делаем это таким образом, что мы можем рассчитывать время O (V), которое лучше, чем O (a (V)), для поиска и объединения множеств в алгоритме Крускаласа за счет | V |пространство, так как нам нужно хранить дополнительное значение для каждой вершины.

Это кажется правильным или я просто бредил временем доступа к массиву?

Answer 1

Ваш алгоритм не работает для A - 1 - B - 3 - C - 2 - D (буквы - вершины, а числа - веса).

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

• У каждой вершины есть индекс в массиве (как и у вас)
• Инициализируйте все элементы массива в -1.Значение массива <0 указывает на корень множества с отрицанием значения, дающего его размер или ранг.Все вершины начинаются в своем собственном наборе размера 1. </li>
• Если значение массива> = 0, это указывает на набор, связанный с родительским набором по этому индексу.Когда вы объединяете два набора, вы устанавливаете значение меньшего в индекс большего и при необходимости корректируете размер большего.Неважно, что вы перезаписываете размер меньшего набора.Он никогда не будет корневым, поэтому вам больше никогда не понадобится размер.