Алгоритм Борувки для минимальных остовных деревьев в Java

Автор оригинала: Sampada Wagde.

1. Обзор

В этом уроке мы рассмотрим Java-реализацию алгоритма Борувки для нахождения минимального связующего дерева (MST) реберно-взвешенного графа .

Он предшествовал алгоритмам Прима и Крускала, но все еще может считаться чем-то средним между ними.

2. Алгоритм Борувки

Мы сразу перейдем к имеющемуся алгоритму. Давайте рассмотрим немного истории, а затем сам алгоритм.

2.1. История

Способ нахождения MST заданного графика был впервые сформулирован Отакаром Борувкой в 1926 году. Это было задолго до того, как появились компьютеры, и фактически было смоделировано для разработки эффективной системы распределения электроэнергии.

Джордж Коллин заново открыл его в 1965 году и использовал в параллельных вычислениях.

2.2. Алгоритм

Центральная идея алгоритма состоит в том, чтобы начать с группы деревьев, каждая вершина которых представляет изолированное дерево. Затем нам нужно продолжать добавлять ребра, чтобы уменьшить количество изолированных деревьев, пока у нас не будет одного связанного дерева.

Давайте рассмотрим это пошагово на примере графика:

• Шаг 0: создайте график
• Шаг 1: начните с группы несвязанных деревьев (количество вершин)
• Шаг 2: пока существуют несвязанные деревья, для каждого несвязанного дерева:
  • найдите его край с меньшим весом
  • добавьте это ребро, чтобы соединить другое дерево

3. Реализация Java

Теперь давайте посмотрим, как мы можем реализовать это в Java.

3.1. Структура данных UnionFind

Для начала нам нужна структура данных для хранения родителей и рангов наших вершин .

Давайте определим класс UnionFind для этой цели с помощью двух методов: union и find :

public class UnionFind {
    private int[] parents;
    private int[] ranks;

    public UnionFind(int n) {
        parents = new int[n];
        ranks = new int[n];
        for (int i = 0; i < n; i++) {
            parents[i] = i;
            ranks[i] = 0;
        }
    }

    public int find(int u) {
        while (u != parents[u]) {
            u = parents[u];
        }
        return u;
    }

    public void union(int u, int v) {
        int uParent = find(u);
        int vParent = find(v);
        if (uParent == vParent) {
            return;
        }

        if (ranks[uParent] < ranks[vParent]) { 
            parents[uParent] = vParent; 
        } else if (ranks[uParent] > ranks[vParent]) {
            parents[vParent] = uParent;
        } else {
            parents[vParent] = uParent;
            ranks[uParent]++;
        }
    }
}

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

Чтобы выяснить принадлежат ли две вершины u и v одному и тому же дереву, мы посмотрим, возвращает ли find(u) тот же родитель, что и find(v) . Метод union используется для объединения деревьев. Мы скоро увидим это использование.

3.2. Введите график От Пользователя

Теперь нам нужен способ получить вершины и ребра графа от пользователя и сопоставить их с объектами, которые мы можем использовать в нашем алгоритме во время выполнения.

Поскольку мы будем использовать JUnit для тестирования нашего алгоритма, эта часть будет описана в методе @Before :

@Before
public void setup() {
    graph = ValueGraphBuilder.undirected().build();
    graph.putEdgeValue(0, 1, 8);
    graph.putEdgeValue(0, 2, 5);
    graph.putEdgeValue(1, 2, 9);
    graph.putEdgeValue(1, 3, 11);
    graph.putEdgeValue(2, 3, 15);
    graph.putEdgeValue(2, 4, 10);
    graph.putEdgeValue(3, 4, 7);
}

Здесь мы использовали График изменяемых значений Гуавы<Целое число, Целое число> для хранения нашего графика. Затем мы использовали Конструктор графиков значений для построения неориентированного взвешенного графика.

Метод помещает значение ребра принимает три аргумента, два Целое число s для вершин и третье Целое число для его веса, как указано в объявлении общего типа MutableValueGraph .

Как мы видим, это тот же вход, что и на нашей диаграмме ранее.

3.3. Выведите Минимальное Связующее Дерево

Наконец, мы подходим к сути вопроса, к реализации алгоритма.

Мы сделаем это в классе, который мы назовем Boruvka MST . Во – первых, давайте объявим пару переменных экземпляра:

public class BoruvkaMST {
    private static MutableValueGraph mst = ValueGraphBuilder.undirected().build();
    private static int totalWeight;
}

Как мы видим, мы используем График изменяемых значений<Целое число, Целое число> здесь, чтобы представить БОЛЬШЕ ВСЕГО.

Во-вторых, мы определим конструктор, в котором будет происходить все волшебство. Для этого требуется один аргумент – график , который мы построили ранее.

Первое, что он делает, – это инициализирует UnionFind вершин входного графа. Изначально все вершины являются их собственными родителями, каждая из которых имеет ранг 0:

public BoruvkaMST(MutableValueGraph graph) {
    int size = graph.nodes().size();
    UnionFind uf = new UnionFind(size);

Затем мы создадим цикл, который определяет количество итераций, необходимых для создания MST – не более V раз в журнале или до тех пор, пока у нас не будет ребер V-1, где V-количество вершин:

for (int t = 1; t < size && mst.edges().size() < size - 1; t = t + t) {
    EndpointPair[] closestEdgeArray = new EndpointPair[size];

Здесь мы также инициализируем массив ребер, closestEdgeArray – для хранения ближайших ребер с меньшим весом.

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

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

for (EndpointPair edge : graph.edges()) {
    int u = edge.nodeU();
    int v = edge.nodeV();
    int uParent = uf.find(u);
    int vParent = uf.find(v);
    
    if (uParent == vParent) {
        continue;
    }

    int weight = graph.edgeValueOrDefault(u, v, 0);

    if (closestEdgeArray[uParent] == null) {
        closestEdgeArray[uParent] = edge;
    }
    if (closestEdgeArray[vParent] == null) {
        closestEdgeArray[vParent] = edge;
    }

    int uParentWeight = graph.edgeValueOrDefault(closestEdgeArray[uParent].nodeU(),
      closestEdgeArray[uParent].nodeV(), 0);
    int vParentWeight = graph.edgeValueOrDefault(closestEdgeArray[vParent].nodeU(),
      closestEdgeArray[vParent].nodeV(), 0);

    if (weight < uParentWeight) {
        closestEdgeArray[uParent] = edge;
    }
    if (weight < vParentWeight) {
        closestEdgeArray[vParent] = edge;
    }
}

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

for (int i = 0; i < size; i++) {
    EndpointPair edge = closestEdgeArray[i];
    if (edge != null) {
        int u = edge.nodeU();
        int v = edge.nodeV();
        int weight = graph.edgeValueOrDefault(u, v, 0);
        if (uf.find(u) != uf.find(v)) {
            mst.putEdgeValue(u, v, weight);
            totalWeight += weight;
            uf.union(u, v);
        }
    }
}

После повторения этих шагов не более V раз или до тех пор, пока у нас не будет ребер V-1, полученное дерево будет нашим MST.

4. Тестирование

Наконец, давайте рассмотрим простой JUnit для проверки нашей реализации:

@Test
public void givenInputGraph_whenBoruvkaPerformed_thenMinimumSpanningTree() {
   
    BoruvkaMST boruvkaMST = new BoruvkaMST(graph);
    MutableValueGraph mst = boruvkaMST.getMST();

    assertEquals(30, boruvkaMST.getTotalWeight());
    assertEquals(4, mst.getEdgeCount());
}

Как мы видим, мы получили БОЛЬШЕ ВСЕГО с весом 30 и 4 ребрами, как и в наглядном примере .

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

В этом уроке мы рассмотрели Java-реализацию алгоритма Борувки. Его временная сложность равна O(E log V), где E-количество ребер, а V-количество вершин .

Как всегда, исходный код доступен на GitHub .