Крускаль против Прима

Мне было интересно, когда следует использовать алгоритм Prim и когда Kruskal's найти минимальное остовное дерево? Оба они имеют легкую логику, одни и те же самые худшие случаи, и только разница - это реализация, которая может включать в себя несколько разных структур данных. Итак, каков решающий фактор?

Ответ 1

Используйте алгоритм Prim, когда у вас есть граф с большим количеством ребер.

Для графа с V вершинами E ребрами алгоритм Kruskal работает в O (E log V), а алгоритм Prim может работать в O (E + V log V), если вы используете Fibonacci Heap.

Алгоритм Prim значительно быстрее в пределе, когда у вас есть действительно плотный граф со множеством других ребер, чем вершины. Kruskal лучше работает в типичных ситуациях (разреженные графики), потому что он использует более простые структуры данных.

Ответ 2

Я нашел очень интересную нить в сети, которая объясняет разницу очень простым способом: http://www.thestudentroom.co.uk/showthread.php?t=232168.

Алгоритм Kruskal будет вырабатывать решение из самого дешевого края, добавляя следующий самый дешевый край, при условии, что он не создает цикл.

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

Здесь приведен интересный лист по этой теме.

Если вы реализуете оба Kruskal и Prim, в их оптимальной форме: с наложением объединения и кучей finbonacci соответственно, то вы заметите, как Kruskal легко реализовать по сравнению с Prim.

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

Ответ 3

Я знаю, что вы не просили об этом, но если у вас больше процессоров, вы всегда должны учитывать алгоритм Borůvka, поскольку он может легко распараллеливаться - следовательно, он обладает преимуществом производительности над алгоритмом Kruskal и Jarník-Prim.

Ответ 4

Kruskal может иметь лучшую производительность, если края можно сортировать по линейному времени или уже отсортированы.

Prim лучше, если число ребер в вершинах велико.

Ответ 5

Если мы остановимся на алгоритме в среднем алгоритме, всегда генерируем связанное дерево, но с другой стороны, kruskal может дать отключенное дерево или лес

Ответ 6

Крускал худший случай сложной сложности O (E log E), потому что нам нужно сортировать ребра. Прим. худший случай сложности O (E log V) с приоритетной очередью или даже лучше, O (E + V log V ) с кучей Фибоначчи. Мы должны использовать Kruskal, когда граф разрежен, т.е. Небольшое число ребер, например E = O (V), когда ребра уже отсортированы или мы можем сортировать их в линейном времени. Мы должны использовать Prim, когда граф плотный, т.е. Число ребер велико, например E = O (V²).

Ответ 7

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

Рассмотрим n вершин и у вас есть полный граф. Чтобы получить ak-кластеры этих n точек. Алгоритм Run Kruskal над первыми n- (k-1) ребрами отсортированного множества ребер. Вы получаете k-кластер график с максимальным интервалом.

Ответ 8

Лучшее время для Крускаля - O (E logV). Для Prim с использованием кувышников мы можем получить O (E + V lgV). Поэтому на плотном графике Prim намного лучше.

Ответ 9

Prim лучше для более плотных графов, и в этом мы также не должны уделять много внимания циклам, добавляя ребро, поскольку мы в основном имеем дело с узлами. Prim быстрее Крускала в случае сложных графов.

Ответ 10

В kruskal Algorithm мы имеем число ребер и число вершин на заданном графике, но на каждом ребре мы имеем некоторое значение или вес, от имени которого мы можем подготовить новый график, который должен быть не циклическим или не близко от какой-либо стороны Для примера