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