Разработка алгоритма, который находит минимальное остовное дерево этого графика в линейном времени

Question

Я работаю над проблемой, в которой мне задан неориентированный граф G на n вершин и с m ребрами, так что каждое ребро e имеет вес w (e) ∈ {1, 2, 3}. Задача состоит в разработке алгоритма, который находит минимальное остовное дерево G в линейном времени (O (n + m)).

Это мои мысли до сих пор:

1. В ходе алгоритмической теории графов, которые я в настоящее время изучает, мы рассмотрели MST алгоритмы Крускала и Прима. Возможно, я могу каким-то образом изменить их, чтобы получить линейное время.
2. Сортировка ребер обычно принимает логарифмический (O (mlog (m))) время; однако, поскольку все веса ребер являются либо 1, 2, либо 3, Bucket Sort может использоваться для сортировки ребер по времени, линейных по числу ребер (O (m)).

Я использую следующую версию алгоритма Крускала:

Kruskal(G) 
    for each vertex ∈ do MAKE−SET() 
    sort all edges in non-decreasing order 
    for edge , ∈ (in the non-decreasing order) do 
    if FIND ≠ FIND() then 
     colour (,) blue 
     UNION(,) 
    od 
    return the tree formed by blue edges 

Кроме того, MAKE-SET (х), UNION (х, у) и FIND (х) определяются следующим образом:

MAKE-SET() 
    Create a new tree rooted at 
    PARENT()=x 

UNION(,) 
    PARENT FIND() ≔() 

FIND() 
    ≔ 
    while ≠ PARENT() do 
    ≔ PARENT() 
    return y 

Проблема, которую я имею в данный момент, состоит в том, что, хотя я могу реализовать первые две строки Крускала в линейном времени, мне не удалось сделать то же самое для следующих четырех строк алгоритма (от «для края» u, ... 'до' UNION (u, v) ').

Буду признателен за то, как реализовать остальную часть алгоритма в линейном времени или как найти модификацию алгоритма Kruskal (или какого-либо другого алгоритма минимального связующего дерева) в линейном времени.

Спасибо.

Answer 1

Если вы используете Disjoint Sets data structure with both path compression and union by rank, вы получаете структуру данных, каждая из которых сложна для каждой операции, очень медленно - это что-то вроде обратного к Ackermann function и не настолько велико для размеров, таких как расчетное число атомов во Вселенной , Эффективно, тогда каждая операция считается постоянным временем, поэтому остальная часть алгоритма также считается линейной.

Из той же статье википедии

Так как α (N) является обратным этой функции, α (п) составляет менее 5 для всех дистанционно практических значений п. Таким образом, амортизированное время работы на операцию фактически является небольшой константой.