Почему алгоритмы Kruskal и Prim MST имеют разное время выполнения для разреженных и плотных графов?

Question

Я пытаюсь понять, почему у Прима и Крускала разные временные сложности, когда речь идет о разреженных и плотных графах. После использования пары апплетов, которые демонстрируют, как работает каждый из них, я все еще немного озадачен тем, как плотность графика влияет на алгоритмы. Я надеюсь, что кто-то может подтолкнуть меня в правильном направлении.

Answer 1

Википедия дает сложность этих алгоритмов с точки зрения E , количества ребер и V , количества вершин, что является хорошей практикой, поскольку позволяет именно такой анализ.

Алгоритм Крускала равен O ( E log V ). Сложность Prim зависит от того, какую структуру данных вы для него используете. Используя матрицу смежности, это O ( V ² ).

Теперь, если вы подключите V ² для E , вот вы получите сложности, которые вы указали в своем комментарии для плотных графиков, и если вы подключите в V для E , вот вы получите редкие.

Почему мы подключаем V ² для плотного графа? Ну, даже на самом плотном графике вы не можете иметь столько ребер V ² , так ясно E = O ( V ) ² ).

Почему мы подключаем V для разреженного графика? Ну, вы должны определить, что вы подразумеваете под разреженным, но предположим, что мы называем граф разреженным, если каждая вершина имеет не более пяти ребер. Я бы сказал, что такие графы довольно редки: как только вы попадете в тысячи вершин, матрица смежности будет в основном пустым пространством. Это будет означать, что для разреженных графов E & le; 5 V , поэтому E = O ( V ).

Answer 2

Являются ли эти разные сложности относительно количества вершин случайно?

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

редактирование:

различные структуры данных также влияют на сложность курса. Википедия разбита на this

Answer 3

Алгоритмы Кормена и др. Действительно дают анализ, в обоих случаях используется разреженное представление графа. С помощью алгоритма Крускала (связывая вершины в непересекающихся компонентах, пока все не соединяется), первым шагом является сортировка ребер графа, что занимает время O (E lg E), и они просто устанавливают, что ничто другое не занимает больше времени, чем это. С помощью алгоритма Прима (расширить текущее дерево, добавив ближайшую вершину, которой еще нет на нем), они используют кучу Фибоначчи для хранения очереди ожидающих вершин и получения O (E + V lgV), потому что с деревом Фибоначчи уменьшается расстояние до вершин. в очереди только O (1), и вы делаете это не более одного раза для каждого ребра.