Мне было интересно, когда следует использовать алгоритм Прима, а когда Крускала, чтобы найти минимальное остовное дерево? Они оба имеют простую логику, одинаковые наихудшие случаи, и единственное различие заключается в реализации, которая может включать в себя несколько разные структуры данных. Так что является решающим фактором?
Используйте алгоритм Прима, когда у вас есть граф с множеством ребер.
Для графа с V вершинами E ребер алгоритм Крускала выполняется за время O (E log V), а алгоритм Прима может работать за время амортизации O (E + V log V) , если вы используете кучу Фибоначчи .
Алгоритм Прима значительно быстрее в пределе, когда у вас действительно плотный граф с гораздо большим числом ребер, чем вершин. Kruskal работает лучше в типичных ситуациях (разреженные графики), потому что он использует более простые структуры данных.
Я нашел в сети очень интересную ветку, которая объясняет разницу очень просто: http://www.thestudentroom.co.uk/showthread.php?t=232168 .
Алгоритм Крускала вырастит решение из самого дешевого ребра, добавив следующее самое дешевое ребро, при условии, что оно не создает цикл.
Алгоритм Прима вырастит решение из случайной вершины путем добавления следующей самой дешевой вершины, вершины, которая в данный момент не находится в решении, но связана с ней самым дешевым ребром.
Здесь прилагается интересный лист на эту тему.
Если вы реализуете и Kruskal, и Prim в их оптимальной форме: с объединением find и кучей finbonacci соответственно, то вы заметите, как Kruskal проще в реализации по сравнению с Prim.
Прим сложнее с кучей Фибоначчи, главным образом потому, что вам нужно вести таблицу бухгалтерского учета для записи двунаправленной связи между узлами графа и узлами кучи. С Union Find, наоборот, структура проста и может даже производить MST напрямую, почти без дополнительных затрат.
источник
V-1края.Я знаю, что вы не просили об этом, но если у вас есть больше единиц обработки, вы всегда должны учитывать алгоритм Боровки , потому что он может быть легко распараллелен - следовательно, он имеет преимущество в производительности по сравнению с алгоритмом Крускала и Ярника-Прима.
источник
Kruskal может иметь лучшую производительность, если края могут быть отсортированы по линейному времени или уже отсортированы.
Прим лучше, если число ребер к вершинам велико.
источник
Наихудший случай сложности времени Крускала - O (E log E) , потому что нам нужно отсортировать ребра. Наихудший случай сложности начального времени - O (E log V) с приоритетной очередью или даже лучше, O (E + V log V) с кучей Фибоначчи . Мы должны использовать Крускала, когда граф разрежен, например, небольшое количество ребер, например E = O (V), когда ребра уже отсортированы или если мы можем отсортировать их за линейное время. Мы должны использовать Prim, когда граф плотный, т.е. число ребер велико, как E = O (V²).
источник
Если мы остановим алгоритм в среднем приме, алгоритм всегда генерирует связанное дерево, но kruskal, с другой стороны, может дать отключенное дерево или лес.
источник
Одним из важных приложений алгоритма Крускала является кластеризация в одном канале .
Рассмотрим n вершин, и вы получите полный граф. Чтобы получить ak кластеров из этих n точек. Алгоритм запуска Крускала по первым n- (k-1) ребрам отсортированного набора ребер. Вы получаете k-кластер графа с максимумом Расстояние между.
источник
Лучшее время для Крускала - это O (E logV). Для Прима, использующего кучи FIB, мы можем получить O (E + V lgV). Поэтому на плотном графе Прима намного лучше.
источник
Прим лучше для более плотных графов, и в этом мы также не должны уделять много внимания циклам, добавляя ребро, так как мы в основном имеем дело с узлами. Прим быстрее, чем Крускал в случае сложных графов.
источник
В алгоритме Крускала у нас есть число ребер и количество вершин на данном графе, но на каждом ребре у нас есть какое-то значение или вес, от имени которого мы можем подготовить новый граф, который не должен быть циклическим или не быть близким с любой стороны. Например
график, как это _____________ | | | | | | | __________ | | Дайте имя любой вершине a, b, c, d, e, f.
источник