algorithm
Алгоритм Крускаля

замечания

Простая, более подробная реализация

Чтобы эффективно обрабатывать обнаружение циклов, мы рассматриваем каждый узел как часть дерева. При добавлении ребра мы проверяем, являются ли его два компонентных узла частью различных деревьев. Первоначально каждый узел составляет одноузловое дерево.

algorithm kruskalMST'(G: a graph)
    sort G's edges by their value
    MST = a forest of trees, initially each tree is a node in the graph
    for each edge e in G:
        if the root of the tree that e.first belongs to is not the same 
        as the root of the tree that e.second belongs to:
            connect one of the roots to the other, thus merging two trees
    
    return MST, which now a single-tree forest

Простая реализация на основе несвязанного набора

Вышеупомянутая методология леса фактически представляет собой структуру данных, не связанных между собой, которая включает в себя три основные операции:

subalgo makeSet(v: a node):
    v.parent = v    <- make a new tree rooted at v
    

subalgo findSet(v: a node):
    if v.parent == v:
        return v
    return findSet(v.parent)

subalgo unionSet(v, u: nodes):
    vRoot = findSet(v)
    uRoot = findSet(u)

    uRoot.parent = vRoot

algorithm kruskalMST''(G: a graph):
    sort G's edges by their value
    for each node n in G:
        makeSet(n)
    for each edge e in G:
        if findSet(e.first) != findSet(e.second):
            unionSet(e.first, e.second)

Эта наивная реализация приводит к времени O(n log n) для управления структурой данных с несвязанными наборами, приводящей к O(m*n log n) времени для всего алгоритма Крускала.

Оптимальная реализация на основе непересекающихся множеств

Мы можем сделать две вещи, чтобы улучшить простые и субоптимальные неагрессивные суб-алгоритмы:

1. Эвристика сжатия findSet : findSet не требует когда-либо обрабатывать дерево с высотой больше 2 . Если он завершает итерацию такого дерева, он может связать нижние узлы напрямую с корнем, оптимизируя будущие обходы;

   subalgo findSet(v: a node):
       if v.parent != v
           v.parent = findSet(v.parent)
       return v.parent
   

2. Эвристическая слияния на основе высоты : для каждого узла сохраняйте высоту своего поддерева. При слиянии сделайте более высокое дерево родителем меньшего, тем самым не увеличивая рост человека.

   subalgo unionSet(u, v: nodes):
       vRoot = findSet(v)
       uRoot = findSet(u)
   
       if vRoot == uRoot:
           return
   
       if vRoot.height < uRoot.height:
           vRoot.parent = uRoot
       else if vRoot.height > uRoot.height:
           uRoot.parent = vRoot
       else:
           uRoot.parent = vRoot
           uRoot.height =  uRoot.height + 1
   

Это приводит к O(alpha(n)) времени для каждой операции, где alpha является обратной для быстрорастущей функции Аккермана, поэтому она очень медленно растет и может быть рассмотрена O(1) для практических целей.

Это делает весь алгоритм Крускала O(m log m + m) = O(m log m) из-за начальной сортировки.

Заметка

Сжатие пути может уменьшить высоту дерева, поэтому сравнение высот деревьев во время операции объединения может не быть тривиальной задачей. Следовательно, чтобы избежать сложности хранения и вычисления высоты деревьев, результирующий родитель может быть выбран случайным образом:

    subalgo unionSet(u, v: nodes):
        vRoot = findSet(v)
        uRoot = findSet(u)

        if vRoot == uRoot:
            return
        if random() % 2 == 0:
            vRoot.parent = uRoot
        else:
            uRoot.parent = vRoot

На практике этот рандомизированный алгоритм вместе с сжатием пути для операции findSet приведет к сопоставимой производительности, но намного проще реализовать.

Простая реализация на высоком уровне

Сортируйте ребра по значению и добавьте каждый в MST в отсортированном порядке, если он не создает цикл.

algorithm kruskalMST(G: a graph)
    sort G's edges by their value
    MST = an empty graph
    for each edge e in G:
        if adding e to MST does not create a cycle:
            add e to MST

    return MST