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

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

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

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

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

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

] Случайно ли это разные сложности с количеством вершин?[

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

]редактирования: [

] различные структуры данных будут также влиять на сложность, конечно, Википедия имеет пробой на [] это [] [

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