streamalism.org

1. Prehľad

V tomto návode sa pozrieme na Java implementáciu Boruvkovho algoritmu na nájdenie Minimum Spanning Tree (MST) okrajovo váženého grafu.

Predchádza Primove a Kruskalove algoritmy, ale stále sa dá považovať za kríženca týchto dvoch algoritmov.

2. Boruvkov algoritmus

Preskočíme priamo do daného algoritmu. Pozrime sa trochu na históriu a potom na samotný algoritmus.

2.1. História

Spôsob, ako nájsť MST daného grafu, prvýkrát formuloval Otakar Boruvka v roku 1926. Bolo to tak ešte predtým, ako vôbec existovali počítače, a bol v skutočnosti modelovaný tak, aby vytvoril efektívny systém distribúcie elektriny.

Georges Sollin ju znovuobjavil v roku 1965 a použil ju v paralelnom výpočte.

2.2. Algoritmus

Ústrednou myšlienkou algoritmu je začať s hromadou stromov, pričom každý vrchol predstavuje izolovaný strom. Potom musíme neustále pridávať hrany, aby sme znížili počet izolovaných stromov, kým nebudeme mať jediný pripojený strom.

Pozrime sa na to v príkladoch s grafom:

• Krok 0: Vytvorte graf
• Krok 1: Začnite s hromadou neprepojených stromov (počet stromov = počet vrcholov)
• Krok 2: zatiaľ čo existujú nespojené stromy, pre každý nespojený strom:
  • nájsť jeho okraj s menšou hmotnosťou
  • pridajte túto hranu na pripojenie iného stromu

3. Implementácia Java

Teraz sa pozrime, ako to môžeme implementovať v Jave.

3.1. The UnionFind Dátová štruktúra

Začať, potrebujeme dátovú štruktúru na ukladanie rodičov a radov našich vrcholov.

Definujme triedu UnionFind na tento účel dvoma spôsobmi: úniea Nájsť:

verejná trieda UnionFind {private int [] rodičia; súkromné ​​int [] hodnosti; public UnionFind (int n) {parent = new int [n]; hodnosti = nový int [n]; pre (int i = 0; i <n; i ++) {rodičia [i] = i; poradie [i] = 0; }} public int find (int u) {while (u! = rodiče [u]) {u = rodičia [u]; } vrátiť u; } public void union (int u, int v) {int uParent = find (u); int vParent = nájsť (v); if (uParent == vParent) {návrat; } if (hodnotí [uParent] hodnotí [vParent]) {rodičia [vParent] = uParent; } else {rodičia [vParent] = uParent; patrí [uParent] ++; }}} 

Túto triedu si môžeme predstaviť ako pomocnú štruktúru na udržiavanie vzťahov medzi našimi vrcholmi a postupné budovanie našej MST.

Zistiť či dva vrcholy u a v patria k rovnakému stromu, uvidíme, či nájsť (u) vráti rovnakého rodiča ako nájsť (v). The únie metóda sa používa na kombinovanie stromov. Toto využitie sa čoskoro dočkáme.

3.2. Vložte graf od používateľa

Teraz potrebujeme spôsob, ako od používateľa získať vrcholy a hrany grafu a namapovať ich na objekty, ktoré môžeme použiť v našom algoritme za behu programu.

Pretože na otestovanie nášho algoritmu použijeme JUnit, táto časť je v a @ Predtým metóda:

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

Tu sme použili guavovskú MutableValueGraph na uloženie nášho grafu. Potom sme použili ValueGraphBuilder na zostrojenie neusmerneného váženého grafu.

Metóda putEdgeValue trvá tri argumenty, dva Celé číslos pre vrcholy a tretí Celé číslo pre svoju hmotnosť, ako je uvedené v MutableValueGraphVšeobecné vyhlásenie o type.

Ako vidíme, jedná sa o rovnaký vstup, aký je zobrazený v našom diagrame z minulosti.

3.3. Odvodiť minimálny rozpätie stromu

Nakoniec sa dostávame k jadru záležitosti, k implementácii algoritmu.

Urobíme to v triede, ktorej zavoláme BoruvkaMST. Najprv deklarujme niekoľko inštančných premenných:

verejná trieda BoruvkaMST {private static MutableValueGraph mst ​​= ValueGraphBuilder.undirected (). build (); private static int totalWeight; } 

Ako vidíme, využívame MutableValueGraph tu zastupovať MST.

Po druhé, definujeme konštruktor, v ktorom sa stane všetka mágia. Vyžaduje si to jeden argument - graf sme postavili skôr.

Prvá vec, ktorú urobí, je inicializácia a UnionFind vrcholov vstupného grafu. Spočiatku sú všetky vrcholy ich vlastní rodičia, každý s hodnotením 0:

public BoruvkaMST (graf MutableValueGraph) {int size = graph.nodes (). size (); UnionFind uf = nový UnionFind (veľkosť); 

Ďalej vytvoríme slučku, ktorá definuje počet iterácií potrebných na vytvorenie MST - najviac log V krát alebo kým nebudeme mať hrany V-1, kde V je počet vrcholov:

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

Tu tiež inicializujeme pole hrán, najbližšieEdgeArray - na uloženie najbližších, menej zaťažených okrajov.

Potom definujeme vnútorné pre slučka na iteráciu cez všetky okraje grafu, aby sa vyplnili naše najbližšieEdgeArray.

Ak sú rodičia dvoch vrcholov rovnakí, je to ten istý strom a nepridávame ho do poľa. V opačnom prípade porovnáme váhu aktuálnej hrany s hmotnosťou okrajov jej nadradených vrcholov. Ak je menšia, potom ju pridáme k najbližšieEdgeArray:

pre (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) {pokračovať; } int vaha = graph.edgeValueOrDefault (u, v, 0); if (nearestEdgeArray [uParent] == ​​null) {najbližšíEdgeArray [uParent] = hrana; } if (najbližšíEdgeArray [vParent] == ​​null) {najbližšíEdgeArray [vParent] = hrana; } int uParentWeight = graph.edgeValueOrDefault (najbližšíEdgeArray [uParent] .nodeU (), najbližšíEdgeArray [uParent] .nodeV (), 0); int vParentWeight = graph.edgeValueOrDefault (nejbližšíEdgeArray [vParent] .nodeU (), najbližšíEdgeArray [vParent] .nodeV (), 0); if (váha <uParentWeight) {najbližšíEdgeArray [uParent] = hrana; } if (váha <vParentWeight) {najbližšíEdgeArray [vParent] = hrana; }} 

Potom definujeme druhú vnútornú slučku, aby sme vytvorili strom. Do tohto stromu pridáme okraje z vyššie uvedeného kroku bez toho, aby sme dvakrát pridali ten istý okraj. Ďalej vykonáme a únie na našom UnionFind odvodiť a uložiť rodičov a stupne vrcholov novovytvorených stromov:

for (int i = 0; i <size; i ++) {EndpointPair edge = nearestEdgeArray [i]; if (edge! = null) {int u = edge.nodeU (); int v = edge.nodeV (); int váha = graph.edgeValueOrDefault (u, v, 0); if (uf.find (u)! = uf.find (v)) {mst.putEdgeValue (u, v, váha); celková hmotnosť + = hmotnosť; uf.union (u, v); }}} 

Po opakovaní týchto krokov najviac log V krát, alebo kým nebudeme mať okraje V-1, je výsledný strom náš MST.

4. Testovanie

Na záver sa pozrime na jednoduchý JUnit na overenie našej implementácie:

@Test public void givenInputGraph_whenBoruvkaPerformed_thenMinimumSpanningTree () {BoruvkaMST boruvkaMST = nová BoruvkaMST (graf); MutableValueGraph mst ​​= boruvkaMST.getMST (); assertEquals (30, boruvkaMST.getTotalWeight ()); assertEquals (4, mst.getEdgeCount ()); } 

Ako vidíme, dostali sme MST s hmotnosťou 30 a 4 hranami, to isté ako obrazový príklad.

5. Záver

V tomto tutoriáli sme videli implementáciu Java algoritmu Boruvka v jazyku Java. Jeho časová zložitosť je O (E log V), kde E je počet hrán a V je počet vrcholov.

Ako vždy, zdrojový kód je k dispozícii na GitHub.