Сложность алгоритмов Prim и Kruskal

Question

Учитывая неориентированный связанный граф с весами. w: E -> {1,2,3,4,5,6,7} - это означает, что возможно только 7 весов. Мне нужно найти связующее дерево, используя алгоритм Прима в O (n + m) и алгоритм Крускаля в O (m * a (m, n)).

Я понятия не имею, как это сделать и действительно нужно руководствоваться тем, как вес может помочь мне здесь.

Answer 1

Как я понимаю, это не популярно, чтобы ответить на домашние задания, но это можно надеяться, будет полезным для других людей, чем только вам;)

Прима:

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

Краткое резюме алгоритма:

1. Создать набор, A, который будет содержать выбранные вершины,. Сначала будет выбран случайный пусковой узел, выбранный вами.
2. Создать другой набор, B. Сначала он будет пустым и будет использоваться для отметки всех выбранных ребер.
3. Выберите ребро E (u, v), то есть ребро от узла u до узла v. Край E должен быть ребром с наименьшим весом, который имеет узел u внутри множества A и v не находится внутри A. (Если имеется несколько ребер с одинаковым весом, любой из них может быть выбран случайным образом)
4. Добавьте ребро (u, v) в множество B и v к набору A.
5. Повторите шаги 3 и 4 до A = V, где V - множество всех вершин.
6. Набор A и B теперь описывают вас, окутывая дерево! MST будет содержать узлы внутри A и B, которые будут описывать, как они соединяются.

Крускала:

Крускала подобен Прима, за исключением того, у вас нет разреза. Поэтому вы всегда выбирали самый маленький край.

1. Создайте набор A, который изначально пуст. Он будет использоваться для хранения выбранных ребер.
2. Выберем край E с минимальным весом из набора E, который еще не находится в A. (u, v) = (v, u), поэтому вы можете пересекать край только в одном направлении.
3. Добавить E в A.
4. Повторите 2 и 3 до тех пор, пока A и E не будут равны, то есть пока вы не выбрали все ребра.

Я не уверен в точности выполнения этих алгоритмов, но я полагаю, что Kruskal - это O (E log E), а производительность Prim основана на структуре данных, которую вы используете для хранения ребер.Если вы используете двоичную кучу, поиск наименьшего края выполняется быстрее, чем если вы используете матрицу смежности для хранения минимального края.

Надеюсь, это поможет!

Answer 2

Вы можете быстрее сортировать грузы.

В алгоритме Kruskal вам не нужно сортировать O (M lg M), вы просто можете использовать сортировку count (или любой другой алгоритм O (M)). Таким образом, конечной сложностью является то, что O (M) для сортировки и O (Ma (m)) для фазы объединения. Всего это O (Ma (m)).

Для случая алгоритма Prim. Вам не нужно использовать кучу, вам нужно 7 списков/очередей/массивов/все (с постоянной вставкой и извлечением времени), по одному на каждый вес. И тогда, когда вы ищете самый дешевый исходящий край, вы проверяете, является ли один из этих списков непустым (от самого дешевого) и используйте этот край. Поскольку 7 - постоянная, все алгоритмы выполняются в O (M) времени.