Алгоритм Крускала для связующих деревьев с реализацией Java

Автор оригинала: Gang Wu.

1. Обзор

В предыдущей статье мы представили алгоритм Прима для поиска минимальных остовных деревьев . В этой статье мы будем использовать другой подход, алгоритм Крускала, для решения задач минимального и максимального остовного дерева.

2. Связующее дерево

Связующее дерево неориентированного графа-это связный подграф, который охватывает все узлы графа с минимально возможным количеством ребер. В общем случае граф может иметь более одного связующего дерева. На следующем рисунке показан график с остовным деревом (края остовного дерева выделены красным цветом):

Если граф взвешен по ребрам, мы можем определить вес остовного дерева как сумму весов всех его ребер. Минимальное связующее дерево-это связующее дерево, вес которого наименьший среди всех возможных связующих деревьев. На следующем рисунке показано минимальное связующее дерево на графе, взвешенном по ребрам:

Аналогично, максимальное связующее дерево имеет наибольший вес среди всех связующих деревьев. На следующем рисунке показано максимальное связующее дерево на взвешенном по ребрам графике:

3. Алгоритм Крускала

Учитывая график, мы можем использовать алгоритм Крускала, чтобы найти его минимальное связующее дерево. Если число узлов в графе равно V , то каждое из его остовных деревьев должно иметь ребра (V-1) и не содержать циклов. Мы можем описать алгоритм Крускала в следующем псевдокоде:

Initialize an empty edge set T. 
Sort all graph edges by the ascending order of their weight values. 
foreach edge in the sorted edge list
    Check whether it will create a cycle with the edges inside T.
    If the edge doesn't introduce any cycles, add it into T. 
    If T has (V-1) edges, exit the loop. 
return T

Давайте шаг за шагом запустим алгоритм Крускала для минимального связующего дерева на нашем примере графа:

Во-первых, мы выбираем ребро (0, 2), потому что оно имеет наименьший вес. Затем мы можем добавить ребра (3, 4) и (0, 1), поскольку они не создают никаких циклов. Теперь следующий кандидат-ребро (1, 2) с весом 9. Однако, если мы включим это ребро, мы получим цикл (0, 1, 2). Поэтому мы отбрасываем это ребро и продолжаем выбирать следующее наименьшее. Наконец, алгоритм завершается добавлением ребра (2, 4) веса 10.

Чтобы вычислить максимальное связующее дерево, мы можем изменить порядок сортировки на порядок убывания. Остальные шаги остаются прежними. На следующем рисунке показано пошаговое построение максимального связующего дерева на нашем образце графика.

4. Обнаружение циклов с непересекающимся набором

В алгоритме Крускала важнейшей частью является проверка того, создаст ли ребро цикл, если мы добавим его к существующему набору ребер. Существует несколько алгоритмов обнаружения циклов графа, которые мы можем использовать. Например, мы можем использовать алгоритм поиска по глубине (DFS) для обхода графика и определения наличия цикла.

Однако нам нужно делать обнаружение цикла на существующих ребрах каждый раз, когда мы тестируем новое ребро. Более быстрым решением является использование алгоритма поиска объединения с непересекающейся структурой данных, поскольку он также | использует метод инкрементного добавления ребер для обнаружения циклов. Мы можем вписать это в наш процесс построения связующего дерева.

4.1. Построение непересекающегося множества и связующего дерева

Во-первых, мы рассматриваем каждый узел графа как отдельный набор, содержащий только один узел. Затем, каждый раз, когда мы вводим ребро, мы проверяем, находятся ли его два узла в одном наборе. Если ответ “да”, то это создаст цикл. В противном случае мы объединяем два непересекающихся набора в один набор и включаем ребро для связующего дерева.

Мы можем повторять описанные выше шаги до тех пор, пока не построим все связующее дерево.

Например, в приведенной выше минимальной конструкции связующего дерева у нас сначала есть 5 наборов узлов: {0}, {1}, {2}, {3}, {4}. Когда мы проверяем первое ребро (0, 2), его два узла находятся в разных наборах узлов. Поэтому мы можем включить это ребро и объединить {0} и {2} в один набор {0, 2}.

Мы можем выполнить аналогичные операции для ребер (3, 4) и (0, 1). Затем наборы узлов становятся {0, 1, 2} и {3, 4}. Когда мы проверяем следующее ребро (1, 2), мы видим, что оба узла этого ребра находятся в одном наборе. Поэтому мы отбрасываем это ребро и продолжаем проверять следующее. Наконец, ребро (2, 4) удовлетворяет нашему условию, и мы можем включить его в минимальное связующее дерево.

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

Мы можем использовать древовидную структуру для представления непересекающегося множества. Каждый узел имеет указатель parent для ссылки на его родительский узел. В каждом наборе есть уникальный корневой узел, представляющий этот набор. Корневой узел имеет указатель parent с собственной ссылкой.

Давайте используем класс Java для определения информации о непересекающихся наборах:

public class DisjointSetInfo {
    private Integer parentNode;
    DisjointSetInfo(Integer parent) {
        setParentNode(parent);
    }
 
    //standard setters and getters
}

Давайте обозначим каждый узел графа целым числом, начиная с 0. Мы можем использовать структуру данных списка, List<Непересекающийся набор В> узлы , для хранения информации о непересекающемся наборе графа. В начале каждый узел является репрезентативным членом своего собственного набора:

void initDisjointSets(int totalNodes) {
    nodes = new ArrayList<>(totalNodes);
    for (int i = 0; i < totalNodes; i++) {
        nodes.add(new DisjointSetInfo(i));
    }
}

4.3. Найти операцию

Чтобы найти набор, к которому принадлежит узел, мы можем следовать по родительской цепочке узла вверх, пока не достигнем корневого узла:

Integer find(Integer node) {
    Integer parent = nodes.get(node).getParentNode();
    if (parent.equals(node)) {
        return node;
    } else {
        return find(parent);
    }
}

Можно иметь сильно несбалансированную древовидную структуру для непересекающегося множества. Мы можем улучшить операцию find , используя метод p ath сжатия .

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

Integer pathCompressionFind(Integer node) {
    DisjointSetInfo setInfo = nodes.get(node);
    Integer parent = setInfo.getParentNode();
    if (parent.equals(node)) {
        return node;
    } else {
        Integer parentNode = find(parent);
        setInfo.setParentNode(parentNode);
        return parentNode;
    }
}

4.4. Деятельность Профсоюза

Если два узла ребра находятся в разных наборах, мы объединим эти два набора в один. Мы можем достичь этой операции union , установив корень одного репрезентативного узла на другой репрезентативный узел:

void union(Integer rootU, Integer rootV) {
    DisjointSetInfo setInfoU = nodes.get(rootU);
    setInfoU.setParentNode(rootV);
}

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

Поскольку именно глубина дерева влияет на время выполнения операции find |/, мы прикрепляем набор с более коротким деревом к набору с более длинным деревом. Этот метод увеличивает глубину объединенного дерева только в том случае, если исходные два дерева имеют одинаковую глубину.

Чтобы достичь этого, мы сначала добавим свойство rank в класс Disjoint Set Info :

public class DisjointSetInfo {
    private Integer parentNode;
    private int rank;
    DisjointSetInfo(Integer parent) {
        setParentNode(parent);
        setRank(0);
    }
 
    //standard setters and getters
}

В начале один узел непересекающийся имеет ранг 0. Во время объединения двух наборов корневой узел с более высоким рангом становится корневым узлом объединенного набора. Мы увеличиваем ранг нового корневого узла на единицу только в том случае, если исходные два ранга совпадают:

void unionByRank(int rootU, int rootV) {
    DisjointSetInfo setInfoU = nodes.get(rootU);
    DisjointSetInfo setInfoV = nodes.get(rootV);
    int rankU = setInfoU.getRank();
    int rankV = setInfoV.getRank();
    if (rankU < rankV) {
        setInfoU.setParentNode(rootV);
    } else {
        setInfoV.setParentNode(rootU);
        if (rankU == rankV) {
            setInfoU.setRank(rankU + 1);
        }
    }
}

4.5. Обнаружение цикла

Мы можем определить, находятся ли два узла в одном и том же непересекающемся наборе, сравнив результаты двух операций find . Если у них один и тот же репрезентативный корневой узел, то мы обнаружили цикл. В противном случае мы объединяем два непересекающихся набора с помощью операции union :

boolean detectCycle(Integer u, Integer v) {
    Integer rootU = pathCompressionFind(u);
    Integer rootV = pathCompressionFind(v);
    if (rootU.equals(rootV)) {
        return true;
    }
    unionByRank(rootU, rootV);
    return false;
}

Обнаружение цикла, с использованием только метода объединения по рангу , имеет время выполнения O(log V) . Мы можем добиться лучшей производительности с помощью методов сжатия пути и объединения по рангу . Время выполнения равно |/O(α(V)) , где α(V) является обратной функцией Аккермана от общего числа узлов. Это небольшая константа, которая меньше 5 в наших реальных вычислениях.

5. Java-реализация алгоритма Крускала

Мы можем использовать График значений структуру данных в Google Guava для представления графа, взвешенного по ребрам.

Чтобы использовать График значений , нам сначала нужно добавить зависимость Guava в вашего проекта pom.xml файл:

    com.google.guava
    guava
    28.1-jre

Мы можем обернуть вышеуказанные методы обнаружения циклов в класс CycleDetector и использовать его в алгоритме Крускала. Поскольку алгоритмы построения минимального и максимального остовного дерева имеют лишь небольшую разницу, мы можем использовать одну общую функцию для достижения обеих конструкций:

ValueGraph spanningTree(ValueGraph graph, boolean minSpanningTree) {
    Set edges = graph.edges();
    List edgeList = new ArrayList<>(edges);

    if (minSpanningTree) {
        edgeList.sort(Comparator.comparing(e -> graph.edgeValue(e).get()));
    } else {
        edgeList.sort(Collections.reverseOrder(Comparator.comparing(e -> graph.edgeValue(e).get())));
    }

    int totalNodes = graph.nodes().size();
    CycleDetector cycleDetector = new CycleDetector(totalNodes);
    int edgeCount = 0;

    MutableValueGraph spanningTree = ValueGraphBuilder.undirected().build();
    for (EndpointPair edge : edgeList) {
        if (cycleDetector.detectCycle(edge.nodeU(), edge.nodeV())) {
            continue;
        }
        spanningTree.putEdgeValue(edge.nodeU(), edge.nodeV(), graph.edgeValue(edge).get());
        edgeCount++;
        if (edgeCount == totalNodes - 1) {
            break;
        }
    }
    return spanningTree;
}

В алгоритме Крускала мы сначала сортируем все ребра графа по их весам. Эта операция занимает O(ElogE) время, где E – общее количество ребер.

Затем мы используем цикл для просмотра отсортированного списка ребер. На каждой итерации мы проверяем, будет ли цикл сформирован путем добавления ребра в текущий набор ребер связующего дерева. Этот цикл с обнаружением цикла занимает не более O(E log V) времени.

Таким образом, общее время работы составляет O(Log + E Log V) . Поскольку значение E находится в шкале O(V ² ) , временная сложность алгоритма Крускала равна O(ElogE) или O(ElogV) .

6. Заключение

В этой статье мы узнали, как использовать алгоритм Крускала для поиска минимального или максимального остовного дерева графа. Как всегда, исходный код статьи доступен на GitHub .