Мне было интересно, когда следует использовать Prim's algorithm и когда Kruskal's найти минимальное остовное дерево? Оба они имеют легкую логику, одни и те же самые худшие случаи, и только разница - это реализация, которая может включать в себя несколько разных структур данных. Итак, каков решающий фактор?Kruskal vs Prim
Используйте алгоритм Prim, когда у вас есть граф с большим количеством ребер.
Для графа с V вершин E ребер, алгоритм Крускала выполняется в О (Е лог В) время и алгоритм Прима может работать в О (Е + лог V V) амортизируется время, если вы используете Fibonacci Heap.
Алгоритм Прима значительно быстрее в пределе, когда у вас есть действительно плотный граф с большим количеством ребер, чем вершины. Kruskal лучше работает в типичных ситуациях (разреженные графики), поскольку использует более простые структуры данных.
Kruskal может иметь лучшую производительность, если края можно сортировать по линейному времени или уже отсортировать.
Прим лучше, если количество ребер до вершин велико.
Лучшее время для Kruskal's - O (E logV). Для Prim с использованием кувышников мы можем получить O (E + V lgV). Поэтому на плотном графе Прим намного лучше.
Я знаю, что вы не просили об этом, но если у вас больше блоков обработки, вы всегда должны учитывать Borůvka's algorithm, потому что это может быть легко распараллелировано - следовательно, оно имеет преимущество в производительности над алгоритмом Kruskal и Jarník-Prim.
Если остановить алгоритм в алгоритме промежуточной Примы всегда порождает связное дерево, но Крускали с другой стороны может дать отключенное дерево или лес
Одним из важных приложений алгоритма Крускал в одной кластеризации связи.
Рассмотрим n вершин, и у вас есть полный граф. Для получения ak-кластеров из этих n точек. Алгоритм Run Kruskal над первыми n- (k-1) ребрами отсортированного множества ребер. Вы получаете k-кластер из график с максимальным интервалом.
Прим лучше для более плотных графов, и в этом мы также не должны уделять много внимания циклам, добавляя ребро, поскольку мы в основном имеем дело с узлами. Прим быстрее, чем Крускал, в случае сложных графов.
Я нашел очень интересную нить в сети, которая объясняет разницу очень простым способом: http://www.thestudentroom.co.uk/showthread.php?t=232168.
Алгоритм Kruskal разработает решение из самого дешевого края, добавив следующий самый дешевый край при условии, что он не создает цикл.
Алгоритм Прима будет вырабатывать решение из случайной вершины, добавив следующую дешевую вершину - вершину, которая в настоящее время не находится в решении, но связана с ней самым дешевым ребром.
Здесь прилагается интересный лист по этой теме.
Если вы реализуете как Крускала и Прима, в их оптимальной форме: с непересекающихся и finbonacci кучи соответственно, то вы заметите, как Крускала легко реализовать по сравнению с Prim.
Прим более сложный с кучей фибоначчи в основном потому, что вам необходимо вести бухгалтерскую таблицу для записи двунаправленной связи между узлами графа и узлами кучи. С помощью Union Find, все наоборот, структура проста и может даже производить непосредственно mst без каких-либо дополнительных затрат.
Nitpick: последний «слайд» в каждом должен читать «повторять до тех пор, пока у вас не будет остовного дерева»; не до тех пор, пока MST, что-то вроде рекурсивной задачи - как я знаю, что это минимально - вот почему я следую за Prim/Kruskal's для начала! – OJFord
@OllieFord Я нашел эту ветку для поиска простой иллюстрации алгоритмов Prim и Kruskal. Алгоритмы гарантируют, что вы найдете дерево, а это дерево - MST. И вы знаете, что вы нашли дерево, когда у вас есть * точно * 'V-1'. – mikedu95
@ mikedu95 Вы правы, делая то же самое, что и мои предыдущие комментарии, под другим углом. – OJFord
В kruskal Algorithm мы имеем число ребер и число вершин на заданном графе, но на каждом ребре мы имеем некоторое значение или вес, от имени которого мы можем подготовить новый график, который должен быть не циклическим или не близким к любому сторона Для примера
graph like this _____________ | | | | | | | __________ | | Дайте имя любой вершине a, b, c, d, e, f.
Крускал время сложность худший случай O (E войти E), это потому, что нам нужно сортировать края. Прим временная сложность худшем случае О (Е журнала V), с приоритет очереди или даже лучше, О (Е + лог V V) с Фибоначчи кучи. Мы должны использовать Kruskal, когда график разрежен, т. Е. Небольшое количество ребер, например E = O (V), когда ребра уже отсортированы или мы можем сортировать их в линейном времени. Мы должны использовать Prim, когда граф плотен, т. Е. Число ребер велико, например E = O (V²).
Я бы сказал «типичные ситуации» вместо среднего. Я думаю, что это неясный термин для использования, например, что такое «средний размер» хэш-таблицы? без понятия. – yairchu
Не забудьте добавить, что кучи Prim + + Fibonacci дают амортизированное время работы, а не худшее время работы. – SplittingField
@SplittingField: Я действительно считаю, что вы сравниваете яблоки и апельсины. Амортизированный анализ - это простой способ получения измерения функции (так сказать) - будь то худший случай или средний случай, зависит от того, что вы доказываете. На самом деле (как я это просматриваю сейчас), в статье wiki используется язык, который подразумевает, что его * только * используется для анализа наихудшего случая. Теперь, используя такой анализ, вы не можете сделать столь же сильные обещания о стоимости конкретной операции, но к тому моменту, когда алгоритм будет выполнен, он будет действительно O (E + VlogV), даже в худшем случае , – agorenst