Когда я смотрел на очень похожую проблему 3-4 года назад, я не мог найти идеального решения в литературе, на которую смотрел.
Я думаю, уловка состоит в том, чтобы найти «маленькое» подмножество«вероятно хороших» краев, по которым вы можете запустить старый добрый Kruskal.В целом, вероятно, что множество ребер MST можно найти среди множества ребер, которые соединяют каждую вершину с ее k ближайшими соседями, для некоторых небольших k .Эти ребра могут не охватывать график, но если они этого не делают, каждый компонент может быть свернут в одну вершину (выбранную случайным образом), и процесс повторяется.(Для большей точности вместо того, чтобы выбрать одного представителя, который станет новым "супервертексом", выберите небольшое число r представителей и в следующем раунде изучите все r ^ 2 расстояния между2 супервершин, выбирающих минимум.)
k алгоритмы ближайших соседей достаточно хорошо изучены для случая, когда объекты могут быть представлены как векторы в конечномерном евклидовом пространстве, поэтомуесли вы можете найти способ привязать ваши объекты к этому (например, с помощью многомерного масштабирования ), тогда вам может повезти.В частности, отображение в 2D позволяет вычислять диаграмму Вороного, и ребра MST всегда будут между смежными гранями.Но из того, что я прочитал, этот подход не всегда дает хорошие результаты.
В противном случае вы можете найти подходы кластеризации полезными: Кластеризация больших наборов данных в произвольных метрических пространствах - этоодна из немногих статей, которые я обнаружил, в которой явно рассматриваются объекты, которые не обязательно являются конечномерными векторами в евклидовом пространстве, и в котором рассматривается возможность использования вычислительно дорогих функций расстояния.