Алгоритм Прима с реализацией Java

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

1. введение

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

2. Минимальное связующее Дерево

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

Мы начинаем с взвешенного графика, поскольку нет смысла минимизировать общий вес ребер, если эти ребра вообще не имеют веса. Давайте взглянем на примерный график:

Приведенный выше график является взвешенным, неориентированным, связным графом. Вот MST этого графика:

Однако MST графа не является уникальным. Если граф имеет более одного MST, то каждый МАТ имеет одинаковый общий вес ребер.

3. Алгоритм Прима

Алгоритм Прима принимает взвешенный, неориентированный, связный граф в качестве входных данных и возвращает MST этого графа в качестве выходных данных .

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

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

Предполагая, что произвольной вершиной для запуска алгоритма является B, у нас есть три варианта A, C и E. Соответствующие веса ребер равны 2, 2 и 5, поэтому минимум равен 2. В этом случае у нас есть два ребра весом 2, поэтому мы можем выбрать любое из них (неважно, какое). Давайте выберем:

Теперь у нас есть дерево с двумя вершинами A и B. Мы можем выбрать любое из еще не добавленных ребер A или B, которые ведут к необработанной вершине. Итак, мы можем выбрать AC, BC или BE.

Алгоритм Прима выбирает минимум, равный 2, или BC:

Теперь у нас есть дерево с тремя вершинами и тремя возможными ребрами для продвижения вперед: CD, CE или BE. AC не включен, так как он не добавит новую вершину в дерево. Минимальный вес среди этих трех-1.

Однако есть два ребра, каждое из которых весит 1. Следовательно, алгоритм Прима выбирает одно из них (опять же не имеет значения, какое именно) на этом шаге:

Осталась только одна вершина, к которой нужно присоединиться, так что мы можем выбрать из CE и BE. Минимальный вес, который может связать наше дерево с ним, равен 1, и алгоритм Прима выберет его:

Поскольку все вершины входного графа теперь присутствуют в выходном дереве, алгоритм Прима заканчивается. Таким образом, это дерево является БОЛЬШЕЙ частью входного графа.

4. Осуществление

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

public class Edge {

    private int weight;
    private boolean isIncluded = false;

}

Каждое Ребро должно иметь вес , так как алгоритм Prim работает на взвешенных графах. включено показывает, присутствует ли Ребро в минимальном связующем дереве или нет.

Теперь давайте добавим класс Vertex :

public class Vertex {

    private String label = null;
    private Map edges = new HashMap<>();
    private boolean isVisited = false;

}

Каждая Вершина может дополнительно иметь метку . Мы используем карту ребра для хранения связей между вершинами. Наконец, посещается показывает, посещалась ли вершина алгоритмом Prim до сих пор или нет.

Давайте создадим наш класс Prime , в котором мы будем реализовывать логику:

public class Prim {

    private List graph;

}

Списка вершин достаточно для хранения всего графа , потому что внутри каждой Вершины у нас есть Карта<Вершина, ребро> для идентификации всех соединений. Внутри Prim, мы создаем run() метод:

public void run() {
    if (graph.size() > 0) {
        graph.get(0).setVisited(true);
    }
    while (isDisconnected()) {
        Edge nextMinimum = new Edge(Integer.MAX_VALUE);
        Vertex nextVertex = graph.get(0);
        for (Vertex vertex : graph) {
            if (vertex.isVisited()) {
                Pair candidate = vertex.nextMinimum();
                if (candidate.getValue().getWeight() < nextMinimum.getWeight()) {
                    nextMinimum = candidate.getValue();
                    nextVertex = candidate.getKey();
                }
            }
        }
        nextMinimum.setIncluded(true);
        nextVertex.setVisited(true);
    }
}

Мы начинаем с установки первого элемента графа List в качестве посещенного. Первым элементом может быть любая из вершин в зависимости от того, в каком порядке они были добавлены в список в первую очередь. isDisconnected() возвращает true если есть какая-либо вершина не посещенная до сих пор:

private boolean isDisconnected() {
    for (Vertex vertex : graph) {
        if (!vertex.isVisited()) {
            return true;
        }
    }
    return false;
}

В то время как минимальное связующее дерево отключено() , мы перебираем уже посещенные вершины и находим Ребро с минимальным весом в качестве кандидата на nextVertex:

public Pair nextMinimum() {
    Edge nextMinimum = new Edge(Integer.MAX_VALUE);
    Vertex nextVertex = this;
    Iterator> it = edges.entrySet()
        .iterator();
    while (it.hasNext()) {
        Map.Entry pair = it.next();
        if (!pair.getKey().isVisited()) {
            if (!pair.getValue().isIncluded()) {
                if (pair.getValue().getWeight() < nextMinimum.getWeight()) {
                    nextMinimum = pair.getValue();
                    nextVertex = pair.getKey();
                }
            }
        }
    }
    return new Pair<>(nextVertex, nextMinimum);
}

Мы находим минимум всех кандидатов в главном цикле и сохраняем его в nextVertex . Затем мы устанавливаем следующую вершину как посещенную. Цикл продолжается до тех пор, пока не будут посещены все вершины.

В конце/| каждый Край с включен равен true присутствует.

Обратите внимание, что, поскольку next Minimum() перебирает ребра, временная сложность этой реализации составляет O(V ² ) . Если вместо этого мы сохраним ребра в приоритетной очереди (отсортированной по весу), алгоритм будет выполняться в O(E log V) .

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

Итак, теперь, когда у нас есть некоторый код, давайте проверим его на реальном примере. Сначала мы построим наш граф:

public static List createGraph() {
    List graph = new ArrayList<>();
    Vertex a = new Vertex("A");
    ...
    Vertex e = new Vertex("E");
    Edge ab = new Edge(2);
    a.addEdge(b, ab);
    b.addEdge(a, ab);
    ...
    Edge ce = new Edge(1);
    c.addEdge(e, ce);
    e.addEdge(c, ce);
    graph.add(a);
    ...
    graph.add(e);
    return graph;
}

Конструктор класса Prime берет его и сохраняет внутри класса. Мы можем распечатать входной график с помощью метода original Graph toString() :

Prim prim = new Prim(createGraph());
System.out.println(prim.originalGraphToString());

Наш пример выведет:

A --- 2 --- B
A --- 3 --- C
B --- 5 --- E
B --- 2 --- C
C --- 1 --- E
C --- 1 --- D

Теперь мы запускаем алгоритм Prim и выводим результирующее MST с минимальным связующим деревом в метод String() :

prim.run();
prim.resetPrintHistory();
System.out.println(prim.minimumSpanningTreeToString());

Наконец, мы распечатываем наши САМЫЕ:

A --- 2 --- B
B --- 2 --- C
C --- 1 --- E
C --- 1 --- D

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

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