Алгоритъм на Prim с реализация на Java

1. Въведение

В този урок първо научаваме какви са минималните обхващащи дървета. След това ще използваме алгоритъма на Prim, за да го намерим.

2. Минимално обхващащо дърво

Минимално обхващащо дърво (MST) е претеглена, ненасочена, свързана графика, чието общо тегло на ръба е минимизирано чрез премахване на по-тежки ръбове . С други думи, ние поддържаме всички върхове на графиката непокътнати, но можем да премахнем някои ръбове, така че сумата от всички ребра да е минимум.

Започваме с претеглена графика, тъй като няма смисъл да се минимизира общото тегло на ръба, ако тези ръбове нямат никакво тегло. Нека да разгледаме примерна графика:

Горната графика е претеглена, ненасочена, свързана графика. Ето MST на тази графика:

MST на графика обаче не е уникален. Ако графика има повече от един MST, тогава всеки MST има еднакво общо тегло на ръба.

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

Алгоритъмът на Prim взема претеглена, неориентирана, свързана графика като вход и връща MST на тази графика като изход .

Работи по алчен начин . В първата стъпка той избира произволен връх. След това всяка нова стъпка добавя най-близкия връх към дървото, изградено досега, докато не остане прекъснат връх.

Нека стартираме алгоритъма на Prim на тази графика стъпка по стъпка:

Ако приемем, че произволният връх за стартиране на алгоритъма е B, имаме три възможности за избор A, C и E. Съответните тегла на ръбовете са 2, 2 и 5, следователно минимумът е 2. В този случай имаме два ръба с тегло 2, така че можем да изберем един от тях (няма значение кой). Нека да изберем A:

Сега имаме дърво с два върха A и B. Можем да изберем някой от A или B ръбовете, които все още не са добавени, които водят до не добавен връх. И така, можем да изберем AC, BC или BE.

Алгоритъмът на Prim избира минимума, който е 2, или BC:

Сега имаме дърво с три върха и три възможни ръба за движение напред: CD, CE или BE. AC не е включен, тъй като не би добавил нов връх към дървото. Минималното тегло сред тези три е 1.

Обаче има два ръба, които тежат 1. Следователно алгоритъмът на Prim избира един от тях (отново няма значение кой) в тази стъпка:

Остава само един връх, за да се присъединим, така че можем да избираме от CE и BE. Минималното тегло, което може да свърже нашето дърво с него, е 1 и алгоритъмът на Prim ще го избере:

Тъй като всички върхове на входната графика вече присъстват в изходното дърво, алгоритъмът на Prim завършва. Следователно това дърво е MST на входната графика.

4. Изпълнение

Върховете и ръбовете правят графики, така че се нуждаем от структура на данни, за да съхраняваме тези елементи. Нека създадем класа Edge :

public class Edge { private int weight; private boolean isIncluded = false; }

Всеки Edge трябва да има тежест, тъй като алгоритъмът на Prim работи върху претеглени графики. isIncluded показва дали Edge присъства в минималното обхващащо дърво или не.

Сега, нека добавим класа Vertex :

public class Vertex { private String label = null; private Map edges = new HashMap(); private boolean isVisited = false; }

Всеки Vertex може по избор да има етикет . Използваме картата на ръбовете, за да съхраняваме връзки между върховете. И накрая, isVisited показва дали върхът е посетен от алгоритъма на Prim досега или не.

Нека създадем нашия клас Prim, където ще внедрим логиката:

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); } }

Започваме с настройката на първия елемент от графика Списък като посетен. Първият елемент може да бъде всеки от върховете в зависимост от реда, в който са били добавени в списъка на първо място. isDisconnected () връща true, ако има някакъв върх, който не е посетен досега:

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

Докато минималното обхващащо дърво е Dissconnected () , ние се въртим по вече посетените върхове и намираме Edge с минималното тегло като кандидат за 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 . След това задаваме nextVertex като посетен. Цикълът продължава, докато се посетят всички върхове.

Накрая присъства всеки Edge с isIncluded, равен на true .

Обърнете внимание, че тъй като nextMinimum () итерира през краищата, сложността във времето на това изпълнение е O (V2) . Ако вместо това съхраняваме ръбовете в приоритетна опашка (сортирани по тегло), алгоритъмът ще изпълнява в 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; }

Конструкторът на клас 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

Сега изпълняваме алгоритъма на Prim и отпечатваме получения 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. Заключение

В тази статия научихме как алгоритъмът на Prim намира минимално обхващащо дърво на графика. Кодът е достъпен в GitHub.