Алгоритм поиска минимального связующего дерева для графа с весами ребер в {1,2,3}

Question

Недавно я провел некоторое исследование алгоритмов Prims/Kruskals для поиска минимальных остовных деревьев на графиках, и меня интересует следующая проблема :

Пусть G - неориентированный граф на n вершин с m ребрами, так что каждое ребро имеет вес w (e) ∈ {1, 2, 3}. Существует ли алгоритм, который находит минимальное остовное дерево G во времени O (n + m)?

Очевидно, что вы можете просто запустить Prims на графике, и вы получите минимальное остовное дерево, но не в требуемое время.

Я думал, что мы можем начать с добавления каждого края с весом 1 к дереву при условии, что он не создает циклов, как если бы был край веса 1, который не создает циклов, тогда предпочтительнее край вес 2 говорят, и делайте это в порядке возрастания.

Любая помощь по возможным способам разработки алгоритма для этого была бы оценена, и любые реализации (желательно Java, но любой язык приветствуется) были бы очень полезны.

Answer 1

Вы описываете незначительную вариацию алгоритма Крускала, которая делает стоимость сортировки по весу O (m) для m ребер, потому что вам нужно всего лишь поместить края в 3 ведра.

Поскольку остальная часть Kruskal's очень близка к O (m) из-за удивительных свойств disjoint set data structure, вы должны быть в хорошей форме.

Построение самого дерева должно быть O (m), а не O (n + m), как ваша цель, потому что нет необходимости обрабатывать вершины. Например. если у вас несколько ребер на вершинах gazillion, большинство из которых не имеют соединения, последним не нужно увеличивать стоимость алгоритма, если вы будете осторожны в дизайне структуры данных.