Понимание того, когда использовать Prim или Kruskal для минимального остовного дерева.

Question

Я пытаюсь применить алгоритмы Прима или Крускала к определенным ситуациям.Я понимаю, что Prim используется, когда графы плотные (Пример: в качестве матрицы смежности с приоритетной очередью в качестве неупорядоченного массива было бы хорошо для плотного дерева, где E = O(V^2). И Kruskal используется, когда графы редки (Пример: в качестве списка смежности с быстрымсортировать где E = O(V). В чем я не уверен, так это в промежутке между ними. Например, график с умеренным количеством ребер, такой что

E = O(V log V)

Это будет Prim или Kruskal? Я думаю, что это можетбыть одним из них, потому что Prim O(E log V) и Kruskal O(E log E) имеют одинаковые временные сложности.

Answer 1

Алгоритм Прима работает быстрее, если у вас действительно плотный граф с гораздо большим числом ребер, чем вершин.Kruskal работает лучше в разреженных графах. Поскольку алгоритм prim всегда соединяет новую вершину с уже посещенной (старой) вершиной, так что каждый этап представляет собой дерево.Kruskal's позволяет подключаться как «новым» к «новому», так и «старым» к «старому», так что это может привести к созданию схемы, и алгоритм должен проверять их каждый раз.Так что Kruskal имеет большую сложность, чем Prim. Так что это зависит от соотношения вершин числа ребер.

Answer 2

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