Существует ли алгоритм для поиска минимального остовного дерева, которое выполняется за время O (n log k) на графе, который имеет только k различных затрат на ребра?

Question

Такой алгоритм был оставлен в качестве упражнения для читателя в книге по разработке алгоритмов Скины, предположительно, это всего лишь модификация алгоритма Прима ( В его вики-справке упражнение 6-11). Кто-нибудь может разработать такой алгоритм?

Answer 1

Да, проблема должна запрашивать O (m + n log k). Очевидно, что Omega (m) является нижней границей, так как мы не можем даже найти край с самым низким весом, не проверив их все.

Для записи принято, что n обозначает количество вершин, а m - количество ребер.

Наслаждайся моей книгой: -)

Стивен Скиена

Answer 2

Prim с простой очередью приоритетов - O (m + n lg n), где m - количество ребер, а n - количество вершин.Если вы группируете записи с одинаковым приоритетом (например, используете связанные списки), вы автоматически получаете O (m + n lg k).

AFAIK, в данном случае уровень техники O (m), Фредман и Уиллард .