Известна ли эта плотная версия алгоритма Крускала?

Около года назад мы с другом подумали, как реализовать алгоритм Крускала для плотных графов лучше, чем обычная граница (без учета предварительно отсортированных ребер). В частности, мы достигаем во всех случаях, аналогично Prim, когда реализованы с использованием матриц смежности.$O(m \log m)$$\Theta(n^2)$

Я опубликовал немного об алгоритме в своем блоге , включая код на C ++ и тесты, но вот общая идея:

• Поддерживать один репрезентативный узел для каждого подключенного компонента. Первоначально все узлы представляют себя.

• Поддерживайте вектор dist[i]таким образом, чтобы для каждого компонента iимелся самый легкий край пересечения компонента, падающий на i.

• При нахождении самого легкого края, который пересекает перегородки, просто найдите, iкоторый минимизирует вес dist[i]в линейном времени.

• При объединении двух компонентов и измените матрицу смежности , чтобы теперь для всех компонентов k , и отметьте i больше не является представителем его подключенного компонента ( теперь останется только j ).$c_i$$c_j$$A$$A_{i, k} = \min \{A_{i, k}, A_{j, k}\}$$k$$i$$j$

Таким образом, сжатие самого легкого края и обнаружение указанного края могут быть выполнены за линейное время. Мы делаем это $n - 1$ раз, чтобы найти MST. Небольшая бухгалтерия необходима для того, чтобы на самом деле определить, какое преимущество мы хотим добавить к MST, но это не увеличивает сложность. Таким образом, среда выполнения является $\Theta(n^2)$ . Реализация это всего лишь пара циклов for.

Известна ли эта версия Крускала в литературе?

Я не уверен в этом конкретном методе для достижения времени , но два разных метода для выполнения времени Крускала за приведены в моей статье «Быстрая иерархическая кластеризация и другие применения динамических ближайших пар «(SODA 1998, arXiv: cs.DS / 9912014 и J. Experimental Algorithms 2000):$O(n^2)$$O(n^2)$

1. Вместо этого используйте Prim – Dijkstra – Jarník, а затем сортируйте ребра, чтобы получить последовательность вставки, которую дал бы Kruskal, или

2. Используйте структуру данных по ближайшим парам дерева квадрантов, описанную в статье, рассматривая Kruskal как стандартную процедуру агломерационной кластеризации, в которой мы объединяем два ближайших кластера в суперкластер на каждом шаге, причем «самый близкий» определяется как длина самого короткого ребра, соединяющего два кластера. ,

Решение 2 по духу аналогично тому, что вы описываете, но детали того, как отслеживать расстояния между кластерами, немного отличаются. Вы сохраняете строковые минимумы матрицы расстояний кластеров, что позволяет вам сканировать этот список минимумов строк за линейное время, чтобы найти глобальный минимум, в то время как моя статья накладывает квадродерево на одну матрицу и отслеживает минимум в каждой площадь квадри. Ваш метод проще, но менее гибок для некоторых других динамических проблем ближайших пар (это зависит от того факта, что слияние двух кластеров приводит к уменьшению их расстояний до других кластеров, что верно для этой проблемы, но не обязательно для других).

Как я писал в 2011 году в статье в Википедии об алгоритме цепочки ближайших соседей , этот алгоритм также можно использовать для выполнения Крускала за времени. Однако (в отличие от некоторых других применений алгоритма цепочки ближайших соседей) вы не получаете экономии пространства, поэтому (как и метод quadtree и ваш метод) пространство по-прежнему равно . В отличие от сортировки Prim + можно использовать только пространство превышающее необходимое для хранения ввода.$O(n^2)$$O(n^2)$$O(n)$