Модифицированная версия алгоритма Прима с временной сложностью O (kn + m)

Question

Не могли бы вы помочь мне с этой проблемой?

Учитывая неориентированный граф G , связанный с взвешенными дугами, таким образом, что весовые коэффициенты являются целыми числами в [1, K]. Напишите модифицированную версию алгоритма Prim, который возвращает минимальное остовное дерево в O (kn + m) время.

Примечание:

• п представляет число вершин
• м представляет собой число ребер

Answer 1

Вы должны использовать ограниченный диапазон длины кромки. Это поможет вам сохранить приоритетную очередь ребер более эффективно. Имейте в виду, что наиболее важным шагом в алгоритме является поиск края минимального веса, соединяющего дерево, построенное до сих пор, с узлом, еще не добавленным к дереву. Попытайтесь использовать counting sort в качестве вдохновения.