Предположим, что у вас есть ориентированный граф с неотрицательными целочисленными длинами ребер, которые находятся в диапазоне от 0 до U - 1 включительно. Какой самый быстрый алгоритм для вычисления минимального остовного дерева этого графа? Мы все еще можем использовать существующие алгоритмы минимального связующего дерева, такие как алгоритм Крускала O (m log n)) или алгоритм Прима (O (m + n log n)). Тем не менее, для случаев, когда U мало, я думаю, что это можно сделать намного лучше.

Существуют ли какие-либо алгоритмы, которые конкурируют с более традиционными алгоритмами MST, которые способны использовать тот факт, что длины ребер ограничены до некоторого диапазона?

Спасибо!