Разница между Борувкой и Крускалом в нахождении МСТ

Question

Хотелось бы узнать разницу между алгоритмом Борувкаса и алгоритмом Крускала.

Что у них общего:

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

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

Таким образом, кажется, что параллельную Борувку следует делать относительно легко (в отличие от Крускала). Это правда?

Answer 1

В случае алгоритма Крускала, прежде всего, мы хотим отсортировать все ребра от самых дешевых до самых дорогих. Затем на каждом шаге мы удаляем ребро минимального веса, и если оно не создает цикл в нашем графе (который изначально состоит из |V|-1 отдельные вершины), затем мы добавим его в MST. В противном случае мы просто удалим его.

Алгоритм Борувки ищет ближайшего соседа каждого компонента (изначально вершины). Он продолжает выбирать самое дешевое ребро из каждого компонента и добавляет его в наш MST. Когда у нас есть только один подключенный компонент, все готово.

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

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

Answer 2

Ваше описание является точным, но одну деталь можно уточнить: перспектива алгоритма Борувки - это каждый связанный компонент, а не каждый отдельный узел.

Ваша интуиция о распараллеливании также верна - эта статья содержит больше деталей. Выдержка из реферата:

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

Answer 3

Важное отличие алгоритма Борувки от алгоритма Крускала или Прима состоит в том, что с алгоритмом Борувки вам не нужно предварительно сортировать края или поддерживать очередь с приоритетами.

Борувка по-прежнему несет в себе дополнительный коэффициент log N в стоимости, но он делает это, требуя O(log N) проходов по краям.

Вы можете распараллелить алгоритм Борувки, но вы также можете распараллелить сортировку, поэтому я не знаю, имеет ли Борувка какие-либо реальные преимущества по сравнению с Крускалом на практике.