Поиск…


замечания

Алгоритм Крускала - это жадный алгоритм, используемый для поиска минимального связующего дерева (MST) графа. Минимальное остовное дерево - это дерево, которое соединяет все вершины графа и имеет минимальный общий вес края.

Алгоритм Крускаля делает это путем многократного выделения краев с минимальным весом (которые еще не находятся в MST) и добавляет их к окончательному результату, если две вершины, связанные этим ребром, еще не соединены в MST, в противном случае он пропускает это ребро. Union. Поиск структуры данных может использоваться для проверки того, что две вершины уже подключены в MST или нет. Несколько свойств MST заключаются в следующем:

  1. MST графа с n вершинами будет иметь ровно n-1 ребер.
  2. Существует единственный путь от каждой вершины до любой другой вершины.

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

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

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


Modified text is an extract of the original Stack Overflow Documentation
Лицензировано согласно CC BY-SA 3.0
Не связан с Stack Overflow