Когда я должен использовать Kruskal в противоположность Чопорному (и наоборот)?
Установка Список:: MoreUtils от CPAN
Тогда в Вашем коде:
use strict;
use warnings;
use List::MoreUtils qw(uniq);
my @dup_list = qw(1 1 1 2 3 4 4);
my @uniq_list = uniq(@dup_list);
182
задан nbro 20 March 2019 в 05:41
поделиться
2 ответа
Используйте алгоритм Прима, когда у вас есть граф с большим количеством ребер.
Для граф с V вершинами E ребер, алгоритм Краскала работает за O (E log V) времени, а алгоритм Прима может работать за O (E + V log V) амортизированное время, если вы используете кучу Фибоначчи .
Алгоритм Прима значительно быстрее в пределе, когда у вас действительно плотный граф с гораздо большим количеством ребер, чем вершин.
192
ответ дан 23 November 2019 в 06:05
поделиться
Kruskal может иметь лучшую производительность, если ребра могут быть отсортированы за линейное время или уже отсортированы.
Прим лучше, если количество ребер до вершин велико.
22
ответ дан 23 November 2019 в 06:05
поделиться
Другие вопросы по тегам: