1. Введение
В этом уроке мы сначала узнаем, что такое минимальные остовные деревья. После этого мы воспользуемся алгоритмом Прима, чтобы найти его.
2. Минимальное остовное дерево
Минимальное остовное дерево (MST) — это взвешенный неориентированный связный граф, общий вес ребер которого минимизирован за счет удаления более тяжелых ребер . Другими словами, мы сохраняем все вершины графа нетронутыми, но можем удалить некоторые ребра, чтобы сумма всех ребер была минимальной.
Начнем со взвешенного графа, так как нет смысла минимизировать общий вес ребер, если эти ребра вообще не имеют веса. Давайте посмотрим на пример графика:
Приведенный выше граф является взвешенным неориентированным связным графом. Вот 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, и его выберет алгоритм Прима:
Поскольку все вершины входного графа теперь присутствуют в выходном дереве, алгоритм Прима завершается. Следовательно, это дерево является MST входного графа.
4. Реализация
Вершины и ребра составляют графы, поэтому нам нужна структура данных для хранения этих элементов. Создадим класс Edge :
public class Edge {
private int weight;
private boolean isIncluded = false;
}
Каждое ребро должно иметь вес , так как алгоритм Прима работает на взвешенных графах. isIncluded показывает, присутствует ли Edge в минимальном связующем дереве или нет.
Теперь добавим класс Vertex :
public class Vertex {
private String label = null;
private Map<Vertex, Edge> edges = new HashMap<>();
private boolean isVisited = false;
}
Каждая вершина может дополнительно иметь метку . Мы используем карту ребер для хранения соединений между вершинами. Наконец, isVisited показывает, посещалась ли до сих пор вершина алгоритмом Прима или нет.
Давайте создадим наш класс Prim , в котором мы реализуем логику:
public class Prim {
private List<Vertex> graph;
}
Списка вершин достаточно для хранения всего графа, потому что внутри каждой вершины у нас есть Map<Vertex, Edge> для идентификации всех соединений. Внутри 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<Vertex, Edge> candidate = vertex.nextMinimum();
if (candidate.getValue().getWeight() < nextMinimum.getWeight()) {
nextMinimum = candidate.getValue();
nextVertex = candidate.getKey();
}
}
}
nextMinimum.setIncluded(true);
nextVertex.setVisited(true);
}
}
Начнем с установки первого элемента графа List<Vertex> как посещенного. Первым элементом может быть любая из вершин в зависимости от порядка их добавления в список в первую очередь. isDisconnected() возвращает true , если какая-либо вершина еще не посещена:
private boolean isDisconnected() {
for (Vertex vertex : graph) {
if (!vertex.isVisited()) {
return true;
}
}
return false;
}
В то время как минимальное остовное дерево isDisconnected() , мы перебираем уже посещенные вершины и находим ребро с минимальным весом в качестве кандидата на следующую вершину:
public Pair<Vertex, Edge> nextMinimum() {
Edge nextMinimum = new Edge(Integer.MAX_VALUE);
Vertex nextVertex = this;
Iterator<Map.Entry<Vertex,Edge>> it = edges.entrySet()
.iterator();
while (it.hasNext()) {
Map.Entry<Vertex,Edge> 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 . Затем мы устанавливаем nextVertex как посещенный. Цикл продолжается до тех пор, пока не будут посещены все вершины.
В конце присутствует каждое ребро с параметром isIncluded , равным true .
Обратите внимание, что поскольку nextMinimum() выполняет итерацию по краям, временная сложность этой реализации составляет O(V 2 ) . Если вместо этого мы сохраним ребра в приоритетной очереди (отсортированной по весу), алгоритм будет выполняться за O(E log V) .
5. Тестирование
Итак, теперь, когда у нас есть код, давайте проверим его на реальном примере. Сначала построим наш график:
public static List<Vertex> createGraph() {
List<Vertex> 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;
}
Конструктор класса Prim берет его и сохраняет внутри класса. Мы можем распечатать входной график с помощью метода originalGraphToString() :
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
Теперь мы запускаем алгоритм Прима и печатаем полученный MST с помощью метода minimumSpanningTreeToString() :
prim.run();
prim.resetPrintHistory();
System.out.println(prim.minimumSpanningTreeToString());
Наконец, мы распечатываем наш MST:
A --- 2 --- B
B --- 2 --- C
C --- 1 --- E
C --- 1 --- D
6. Заключение
В этой статье мы узнали, как алгоритм Прима находит минимальное остовное дерево графа. Код доступен на GitHub .