Участник:Kanast74/Алгоритм кластеризации, основанный на минимальном покрывающем дереве

Статью подготовила: Дмитриева Анастасия Владимировна.

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

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

Необходимость кластеризовать объекты может возникнуть в любой сфере анализа данных, например, при разделении веб-документов на жанры, а также в задачах распознавания образов и анализа социальных сетей.

Пусть на начальном этапе решения задачи имеются набор тестовых примеров [math]X=\{x_1...x_n\}[/math], а также функция расстояния между ними [math]r(e)[/math]. Отметим, что метрика, в которой вычисляются расстояния между объектами, выбирается исходя из требований задачи; наиболее распространенные - это Евклидово расстояние, квадрат Евклидова расстояния, манхэттенская метрика, расстояние Чебышева и степенное расстояние. Далее необходимо применить один из алгоритмов кластеризации, которые можно разделить на две категории: иерархические, состоящие в последовательном поиске кластеров из уже найденных кластеров, а также неиерархические, цель которых состоит в минимизации некоторой целевой функции. К последней группе относятся такие алгоритмы, как алгоритм k-средних, алгоритм EM, нечеткие алгоритмы, а также алгоритмы теории графов, к категории которых относится алгоритм, описываемый в данной статье.

Рассмотрим алгоритм кластеризации на k кластеров, основанный на построении минимального остовного дерева (MST) и который состоит в следующем:

1. По исходным данным строится взвешенный неориентированный граф: каждый объект представляется в виде вершины графа, а вес ребра, связывающего две вершины, есть расстояние между объектами в выбранной заранее метрике
2. Для полученного графа строится минимальное остовное дерево, то есть дерево, содержащее все вершины графа и имеющее минимальный суммарный вес своих ребер
3. Удаляется k-1 ребро минимального остовного дерева с максимальным весом
4. Получаются k компонент связности, которые интерпретируются как кластеры

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

1. Алгоритм Крускала
2. Алгоритм Борувки
3. Алгоритм Прима

Отметим, что в рамках проведенного исследования использовался алгоритм Крускала, наиболее подробно изучить который можно, пройдя по ссылке [Алгоритм Крускала], поэтому в данной статье его описание не приводится.

1.2 Математическое описание алгоритма

С математической точки зрения задачу кластеризации можно рассматривать как минимизацию среднего внутрикластерного расстояния [math] \frac{\sum_{i\lt j, c(x_i)=c(x_j)} r(x_i,x_j)}{\sum_{i\lt j, c(x_i)=c(x_j)} 1} \to min [/math] с одной стороны и максимизации межкластерного расстояния [math] \frac{\sum_{i\lt j, c(x_i)\neq c(x_j)} r(x_i,x_j)}{\sum_{i\lt j, c(x_i) \neq c(x_j)} 1} \to max [/math] с другой стороны, где [math]c(x)[/math] - кластер, к которому принадлежит объект [math]x[/math].

Применительно к алгоритмам кластеризации, основанным на теории графов, процедура минимизации/максимизации соответствующих расстояний состоит в выборе определенного порогового значения веса ребра [math]w[/math], ребра с весом меньше которого предполагаются связующими для вершин, принадлежащих одному классу, а ребра с весом больше которого предполагаются связующими для вершин, принадлежащих разным классам.

1.3 Вычислительное ядро алгоритма

Вычислительным ядром описываемого алгоритма является построение минимального остовного дерева. В случае, если программа предполагается быть распараллеленной, то операция построения MST будет производиться в отдельности в каждом процессе. Как уже было отмечено, в данном исследовании для построения MST использовался алгоритм Крускала, который будет работать наиболее эффективно, если веса ребер исходного графа отсортированы, поэтому сортировка - это еще одна операция, которая должна быть включена в вычислительное ядро, что предполагает выбранная ревлизация алгоритма. Поэтому в дальнейшем мы не будем разделять сортировку и поиск минимального остовного дерева, предполагая, что они объеденены в единый эффективный алгоритм.

Дадим некоторую справку касательно адгоритма поиска MST, фигурирующего в данном исследовании. Алгоритм Крускала — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые описан Джозефом Крускалом в 1956 году.

Алгоритм Крускала находит безопасное ребро для добавления в растущий лес путем поиска ребра [math](u, v)[/math] с минимальным весом среди всех ребер, соединяющих два дерева в лесу. Обозначим два дерева, соединяемые ребром [math](u, v) [/math], как [math]C_1[/math] и [math]C_2[/math]. [math](u, v)[/math] — безопасное для [math]C_1[/math] ребро. Алгоритм Крускала является жадным, поскольку на каждом шаге он добавляет к лесу ребро с минимально возможным весом.

1.4 Макроструктура алгоритма

1. Построение графа путем задания списков ребер. В общем случае, когда задано некоторое множество объектов, для построения графа может быть использован алгоритм, позволяющий рассчитать расстояние от каждого объекта до каждого за [math]O(n^2)[/math] операций, где [math]n[/math] число объектов (вообще говоря, данная операция требует [math]O(E)[/math] операций, где [math]E[/math] - число ребер в графе, но в нашем случае число ребер подразумевается равным [math]E=\frac{D (n(n-1))}{2}[/math], [math]D[/math] - плотность графа). Однако в рамках данного исследования для тестирования алгоритма использовалась такая технология построения графов, когда в качестве веса каждого ребра назначается некоторое произвольное число из заданного промежутка (например, от 1 до 1000), что также требует [math]O(n^2)[/math]
2. Построение минимального остовного дерева на основании полученного ранее графа, для чего может быть использован один из известных и наиболее распространенных алгоритмов (алгоритм Крускала, алгоритм Борувки или алгоритм Прима). Рассмотрим, например, алгоритм Крускала. На начальном этапе имеется граф, состоящий из вершин - объектов исходной выборки и не содержащий ребер, следовательно, каждая из вершин изначально представляет собой компоненту связности и даже дерево. Алгоритм состоит в выборе на каждом шаге ребра с минимальным весом и добавлении его в дерево, если оно соединяет два дерева. Алгоритм будет работать максимально эффективно, если изначально ребра графа, полученного на первом шаге будут отсортированы (например, по возрастанию).
3. Для получения [math]k[/math] кластеров необходимо удалить из получившегося минимального остовного дерева [math]k-1[/math] ребро с максимальным весом. В частности, в случае, если на предыдущем шаге мы пользовались алгоритмом Крускала для построения MST, ребра получившегося дерева отсортированы по возрастанию, значит для удаления указанных выше ребер потребуется лишь [math]O(1)[/math] операций
4. Наконец, необходимо правильно интерпретировать результат работы алгоритма и перечислить вершины, принадлежащие полученным кластерам; на выполнение данного шага может потребоваться различное число операций в зависимости от формата выходных данных программы: например, в данной реализации выходные данные, как будет сказано в дальнейшем, представлены в виде списка ребер, формирующий итоговый минимальный остовный лес, следовательно в общем случае на его обработку потребуется [math]O(V)[/math] операций

1.4.1 Используемые обозначения и структуры данных

Обозначим в качестве [math]G=(V,E)[/math] граф, содержащий [math]V[/math] вершин и [math]E[/math] ребер. Для построения минимального остовного дерева для данного графа используются три операции [2], опишем здесь каждую из них:

1. операция MakeSet([math]v[/math]) генерирует дерево (множество) для вершины графа [math]v[/math], являющейся корнем искомого дерева
2. операция Find([math]v[/math]) определяет, которому из деревьев принадлежит интересующая вершина [math]v[/math]. Условимся, что данная операция возвращает ту вершину, которая является корнем искомого дерева
3. операция Union([math]u, v[/math]) объединяет два множества (два дерева, содержащих соответствующие вершины) под одним корнем

1.5 Схема реализации последовательного алгоритма

Приведем здесь псевдокод основной части алгоритма - а именно построения локального минимального остовного дерева при помощи алгоритма Крускала.

Kruskal ( G=(V,E) ):

1. mst = ∅;

2. сортировать E по возрастанию;

3. для каждой вершины v из множества вершин V:

4. MakeSet(v);

5. для каждого ребра e = (u, v) из множества ребер E:

6. if Find(u) ≠ Find(v):

7. mst = mst ∪ { (u,v) };

8. Union(u, v);

9. return mst;

1.6 Последовательная сложность алгоритма

Сперва оценим последовательную сложность составных частей алгоритма.

0. O(E): Формирование графа

1. O(1): Инициализация пустого множества.

2. O(Elog(E)): сортировка ребер из множества E.

3. O(V): Инициализация одноточечного множества для каждой вершины из V.

4. ▲ MakeSet за O(1).

5. O(Elog(V)): Операции Union и Find для каждого ребра из E.

6. ▲ Find за O(1).

7. ▲ Присоединение элемента за O(1).

8. ▲ Union за O(log(V)).

9. O(1): Удаление k-1 ребра для получения k компонент связности

10. O(V): Перечисление вершин, входящих в соответствующие кластеры

11. O(1): Return.

Таким образом, с учетом того, что, получаем:

[math]T( G = (V, E) ) = O(1) + O(E\log(E)) + O(V) + O(E\log(V)) + O(E) = O(E\log(E)) + O(E\log(V)) = O(E\log(V)) + O(E\log(V))[/math]

Итак, оценка сложности алгоритма есть [math]T( G = (V, E) ) = O(E\log(V)) + O(\log(V))[/math]

1.7 Информационный граф

Рисунок 1. Информационный граф алгоритма

По структуре информационного графа можно сделать вывод что высота канонической ярусно-параллельной формы [1] есть [math]\log{p}[/math], где [math]p[/math] число процессов.

1.8 Ресурс параллелизма алгоритма

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

Тем не менее, прежде всего следует установить справедливость свойства используемого алгоритма поиска MST, позволяющего произвести его распараллеливание [3]:

Ассоциативность по рёбрам. Пусть [math]MSF(E)[/math] – минимальный остовный лес графа с рёбрами [math]E[/math]. Тогда

[math] MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)). [/math]

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

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

Далее внутри каждой группы объектов (каждый процесс в отдельности) строим минимальное остовное дерево, в конце шага деревья объединяются в одно - общее MST для всех объектов, поддерживая при этом отсортированность расстояний по возрастанию.

Наконец, будем удалять необходимое количество ребер глобального остовного дерева для того, чтобы получить требуемое количество кластеров - компонент связности графа.

1.8.1 Стратегии распараллеливания

Необходимо отметить, что несмотря на всю простоту идеи распараллеливания алгоритма, описанную выше, существует несколько стратегий реализовать ее на практике. При этом, как будет показано далее, указанные стратегии дают различные приросты в производительности. Перечислим некоторые из них:

1. первая стратегия, наиболее очевидная, состоит в том, чтобы в самом начале главный процесс считывает данные о ребрах и распределяет считанную информацию между остальными процессами, не имеющим доступа к файлу с исходными данными. Далее каждый из процессов рассчитывает локальное минимальное остовное дерево и передает его обратно главному процессу, который объединяет деревья в одно, глобальное
2. вторая стратегия во многом напоминает первую, но основное различие между ними состоит в том, что во втором случае файл с исходными данными не разделяется между процессами, а является доступным для каждого из них в полном объеме. Таким образом, каждый процесс способен считать данные о ребрах, за которые они отвечают, самостоятельно, что значительно снижает объем коммуникации между процессами. Также еще одно улучшение состоит в том, что теперь главный процесс не простаивает во время работы остальных, а, как и остальные, рассчитывает локальное минимальное остовное дерево
3. наконец, третья стратегия состоит в том, чтобы оптимизировать процесс слияния локальных минимальных остовных деревьев. Предлагается сделать так, чтобы не только главный процесс занимался слиянием, но каждый процесс участвует в процессе слияния. Для того, чтобы добиться максимальной эффективности будем предполагать, что число процессов [math]p=2^n,n\gt 1[/math]. В этом случае потребуется [math]\log{p}[/math] шагов, чтобы выполнить слияние. На каждом шаге половина активных процессов пересылает свое локальное дерево процессу с меньшим номером на единицу, а другая половина занимается приемом и слиянием. Таким образом, через [math] \log{p} [/math] шагов главный процесс, который имеет номер 0, будет иметь в своем распоряжении глобальное минимальное остовное дерево.

1.8.2 Способы разделения графа

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

Правильный подход к разделению графа на подграфы состоит в том, чтобы каждая из подзадач имела в качестве входных данных связный подграф исходного графа, состоящий из вершин и соединяющих их ребер.

1.9 Входные и выходные данные алгоритма

По исходным данным формируется граф [math]G = (V, E)[/math], являющийся неориентированным, взвешенным, связным и не имеющим кратных ребер. Пусть полученный граф содержит [math] |V|[/math] вершин и [math]|E|[/math] ребер. Предполагая, что каждый объект можно сравнить с каждым, можно считать, что получаемый граф является полным, а значит число ребер может быть оценено следующим образом: [math]|E|=\frac{|V|(|V|-1)}{2} \le \frac{|V|^2}{2}-\frac{|V|}{2} \Rightarrow O(E)=O(V^2)[/math]

Обозначим в виде [math]w(u,v)[/math] вес ребра, соединяющего вершины [math]u[/math] и [math]v[/math]. Тогда граф может быть задан в виде списка ребер, а именно списка троек: [math](u,v,w(u,v))[/math], что является более удобным представлением графа для реализации многих алгоритмов по сравнению с матрицей смежности. Помимо этого, данный способ помогает сэкономить память. Недостатков указанного подхода является только то, что установить, с какими вершинами связана интересующая вершина, а также вес соответствующих ребер является весьма затруднительно. Однако для решения поставленной задачи нам это и не потребуется.

Формат выходных данных аналогичный

1.10 Свойства алгоритма

1.10.1 Вычислительная мощность

Оценим вычислительную мощность алгоритма в том случае, когда для его реализации используется [math]p[/math] процессов. Предположим, что алгоритм реализован при помощи первой стратегии (см. выше) и применяется к графу [math]G = (V, E)[/math], тогда:

• Ввод данных: [math]\frac{|E|}{p}[/math] - в среднем столько ребер содержит получаемый каждым процессом связный подграф
• Вывод данных: [math]\frac{|V| - 1}{p}[/math] - каждый из процессов должен вывести посчитанное локальное минимальное дерево, которое содержит указанное количество ребер, так как остальные ребра, изначально входившие в состав подграфа, не будут входит в локальное MST
• Вычисление: для вычисления локального MST каждому из процессов требуется [math]\frac{|E|}{p} \log{\frac{|V|}{p}}[/math] операций

Таким образом, искомое соотношение может быть записано в следующем виде: [math]\frac{\frac{|E|}{p} \log{\frac{|V|}{p}}}{\frac{|E|}{p} + \frac{|V| - 1}{p}} = \frac{|E| \log{\frac{|V|}{p}}}{|E|+|V|-1}[/math]

На основании полученной формулы можно сделать несколько выводов:

1. так алгоритм сильно зависит от входных данных, с увеличением плотности графа данное соотношение увеличивается, то есть чем более плотным является граф, тем меньшее влияние на время работы алгоритма влияет вычислительная часть
2. следует рационально выбирать количество используемых процессов, так как в случае, если число выбрано слишком большим, время, отводимое на коммуникацию, может превысить время, требуемое для проведение вычислений
3. аналогичное соотношение можно вычислить и в тех случаях, когда применяются вторая и третья описанные выше стратегии. Читателю предлагается самостоятельно вычислить соответствующие соотношения. Заметим только, что исходя из соображений, на основании которых были построены стратегии, время, требуемое для осуществления коммуникаций снизится

1.10.2 Оценка прироста в производительности

1.10.2.1 Закон Амдала

В данном рзеделе будет производиться оценка прироста производительности параллельного алгоритма по сравнению с последовательным. Наиболее простой способ оценить прирост производительности – использовать закон Амдала, который гласит, что прирост может быть оценен следующим образом: [math] S_p \le \frac{1}{f+\frac{1-f}{p}}[/math]

Где [math]f[/math] – часть алгоритма, которая не может быть распараллелена, [math]p[/math] – число процессов.

В наиболее тривиальном случае (первая стратегия распараллеливания) распараллеливанию не подлежит считывание входных данных и их разделение между процессами, а также объединение локальных MST в одно. Поэтому сложность последовательной части программы может быть оценена следующим образом: [math]2O(V^2)+O(V^2 \log{V})[/math]. Распараллеливанию подлежит инициализация подграфов при помощи операции MakeSet за [math]O(V)[/math], сортировка ребер по возрастанию внутри каждой группы за [math]O(V^2 \log{V})[/math], а также построение локальных минимальных остовных деревьев за аналогичное время. Поэтому сложность параллельной части алгоритма может быть оценена так: [math]O(V)+2 O(V^2 \log{V})[/math]. Таким образом, вычислив отношение сложностей частей программы, получаем, что [math]f=0.44[/math]. Устремим число процессов [math]p[/math] к бесконечности и получим, что максимальное ускорение, которое можно получить путем распараллеливания алгоритма есть [math]2.27[/math]. К сожалению, данная оценка не является точной. Для того, чтобы оценить прирост производительности более качественно, произведем анализ временных диаграмм программы.

1.10.2.2 Анализ временных диаграмм

Обозначим за [math]t_d[/math] – время, которое требуется для того, чтобы разделить граф на подграфы, [math]t_p[/math] – суммарное время вычислений, [math]t_b[/math] – время обратной пересылки локально полученных результатов, [math]t_l[/math] – задержка одной пересылки. Причем можно убедиться в том, что [math]t_p \gt t_d \gt t_b \gt t_l[/math], также известно, что время выполнения последовательного кода [math]t_{serial} = t_p[/math].

Рисунок 2. Первая стратегия распараллеливания вычислительного ядра алгоритма

Произведем анализ первой (наивной) стратегии распараллеливания программы. На временной диаграмме жирным обозначен критический путь, время выполнения которого может быть вычислено по формуле:[math]t_{paralel} = 4 t_l + t_d + \frac{t_p}{3} + \frac{t_b}{3}[/math]

Тогда максимальное ускорение для одного процесса есть: [math]speedup=\frac{t_{serial}}{t_{parallel}} = \frac{t_p}{4 t_l + t_d + \frac{t_p}{3} + \frac{t_b}{3}}[/math]

А в случае n процессов: [math]speedup = \frac{n}{1+\frac{n (n+1) t_l + n t_d + t_b}{t_p}}[/math]

Рисунок 3. Вторая стратегия распараллеливания вычислительного ядра алгоритма

Теперь проанализируем вторую стратегию, основная задача которой – уменьшить объем коммуникаций между процессами за счет того, что файл с исходными данными теперь доступен всем процессам. Помимо этого введем в рассмотрение новую величину [math]t_i[/math] – время, требующееся на инициализацию множеств вершин. Тогда для одного процесса [math]t_{parallel} = t_i + \frac{t_p}{4} + t_l + 3 \frac{t_b}{4}[/math], а максимальное ускорение в случае n процессов есть: [math]speedup= \frac{t_{serial}}{t_{parallel}} = \frac{4}{1+\frac{4 t_i + 4 t_l + 3 t_b}{t_p}}[/math]

Рисунок 4. Третья стратегия распараллеливания вычислительного ядра алгоритма

Наконец, проанализируем третью стратегию, основная цель которой – оптимизировать процесс слияния локальных минимальных остовных деревьев, а также привлечь все активные процессы (включая главный) к процессу построения локального MST. В этом случае время выполнения параллельной части программы с использованием лишь одного процесса: [math] t_{parallel}=t_i + \frac{t_p}{4} + t_l + 2 \frac{t_b}{4}[/math], а суммарное ускорение в общем случае: [math]speedup=\frac{t_{serial}}{t_{parallel}} = \frac{n}{1+\frac{n t_i + n t_l + \log_2{n} t_b}{t_p}}[/math]

На рисунке 5 приведены графики, отражающие зависимость получаемых возможных ускорений в зависимости от числа задействованных процессов, посчитанные с использованием четырех различных подходов.

Рисунок 5. Сравнение стратегий распараллеливания

2 Программная реализация алгоритма

2.3 Возможные способы и особенности параллельной реализации алгоритма

Необходимо отметить, что несмотря на всю простоту идеи распараллеливания алгоритма, описанную выше, существует несколько стратегий реализовать ее на практике. При этом, как будет показано далее, указанные стратегии дают различные приросты в производительности. Перечислим некоторые из них:

1. первая стратегия, наиболее очевидная, состоит в том, чтобы в самом начале главный процесс считал данные о ребрах и распределил считанную информацию между остальными процессами, причем каждый из них не имеет доступа к файлу с данными. Далее каждый из процессов рассчитывает локальное минимальное остовное дерево и передает его обратно главному процессу, который объединяет деревья в одно, глобальное
2. вторая стратегия во многом напоминает первую, но основное различие между ними состоит в том, что во втором случае файл с исходными данными не разделяется между процессами, а является доступным для каждого из них в полном объеме. Таким образом, каждый процесс способен считать данные о ребрах, за которые они отвечают, самостоятельно, что значительно снижает объем коммуникации между процессами. Также еще одно улучшение состоит в том, что теперь главный процесс не простаивает во время работы остальных, а, как и остальные, рассчитывает локальное минимальное остовное дерево
3. наконец, третья стратегия состоит в том, чтобы оптимизировать процесс слияния локальных минимальных остовных деревьев. Предлагается сделать так, чтобы не только главный процесс занимался слиянием, но каждый процесс участвует в процессе слияния. Для того, чтобы добиться максимальной эффективности будем предполагать, что число процессов [math]p=2^n,n\gt 1[/math]. В этом случае потребуется [math]\log{p}[/math] шагов, чтобы выполнить слияние. На каждом шаге половина активных процессов пересылает свое локальное дерево процессу с меньшим номером на единицу, а другая половина занимается приемом и слиянием. Таким образом, через шагов главный процесс, который имеет номер 0, будет иметь в своем распоряжении глобальное минимальное остовное дерево.

2.4 Масштабируемость алгоритма и его реализации

Рисунок 6. График зависимости времени вычисления от размера задачи и числа процессов (с учетом времени ввода-вывода)

Рисунок 7. График зависимости времени вычисления от размера задачи и числа процессов (без учета времени ввода-вывода)

На графиках видно, как с увеличением объема вычислительных ресурсов происходит прирост в производительности. Данный эффект происходит до некоторых пор, после чего накладные расходы на коммуникацию между процессами нивелируют его. При дальнейшем увеличении числа процессов время решения задачи заметно увеличивается, однако, ввиду длинных очередей на суперкомпьютере Ломоносов данные с числом процессов [math] \ge 256[/math] получить не удалось

2.7 Существующие реализации алгоритма

• C++: Boost Graph Library (функция kruskal_min_spanning_tree).
• C++, MPI: Parallel Boost Graph Library
  • функция merge_local_minimum_spanning_trees реализует алгоритм Крускала;
  • функции dense_boruvka_minimum_spanning_tree, boruvka_then_merge, boruvka_mixed_merge сочетают алгоритм Борувки и алгоритм Крускала.
• Python: NetworkX (функция minimum_spanning_tree).
• Java: JGraphT (класс KruskalMinimumSpanningTree).

3 Литература

[1] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[2] http://www.gpiskas.com/pdf/kruskal_mpi.pdf (дата обращения: 02.10.2016)