streamalism.org

1. Pregled

U ovom vodiču, pogledati ćemo Java implementaciju Boruvkinog algoritma za pronalaženje stabla minimalnog opsega (MST) grafa ponderiranog rubom.

Prethodi Primovim i Kruskalovim algoritmima, ali se ipak može smatrati križanjem između njih dvojice.

2. Boruvkin algoritam

Skočit ćemo ravno u algoritam koji je pri ruci. Pogledajmo malo povijesti, a zatim i sam algoritam.

2.1. Povijest

Način pronalaska MST-a datog grafa prvi je formulirao Otakar Boruvka 1926. godine. To je bio put prije nego što su računala uopće postojala, a zapravo je oblikovan za dizajn učinkovitog distribucijskog sustava električne energije.

Georges Sollin ponovno ga je otkrio 1965. i koristio u paralelnom računanju.

2.2. Algoritam

Središnja ideja algoritma je započeti s hrpom stabala sa svakim vrhom koji predstavlja izolirano stablo. Zatim moramo nastaviti dodavati rubove kako bismo smanjili broj izoliranih stabala dok ne dobijemo jedno povezano stablo.

Pogledajmo ovo u koracima s primjerom grafikona:

• Korak 0: stvorite grafikon
• Korak 1: započnite s hrpom nepovezanih stabala (broj stabala = broj vrhova)
• Korak 2: dok postoje nepovezana stabla, za svako nepovezano stablo:
  • pronaći njegov rub s manjom težinom
  • dodaj ovaj rub za povezivanje drugog stabla

3. Implementacija Jave

Sada da vidimo kako to možemo implementirati u Javi.

3.1. The UnionFind Struktura podataka

Za početak, potrebna nam je struktura podataka za pohranu roditelja i redova naših vrhova.

Definirajmo razred UnionFind u tu svrhu, s dvije metode: unija, i pronaći:

javni razred UnionFind {private int [] roditelji; privatni int [] redovi; javni UnionFind (int n) {roditelji = novi int [n]; redovi = novi int [n]; za (int i = 0; i <n; i ++) {roditelji [i] = i; rang [i] = 0; }} javni int find (int u) {while (u! = roditelji [u]) {u = roditelji [u]; } povratak u; } javni void union (int u, int v) {int uParent = find (u); int vParent = pronađi (v); if (uParent == vParent) {return; } if (rangira [uParent] rangira [vParent]) {roditelji [vParent] = uParent; } else {roditelji [vParent] = uParent; redovi [uParent] ++; }}} 

O ovoj klasi možemo razmišljati kao o pomoćnoj strukturi za održavanje odnosa između naših vrhova i postupnu izgradnju našeg MST-a.

Saznati da li dva vrha u i v pripadaju istom drvetu, vidimo da li naći (u) vraća istog roditelja kao pronaći (v). The unija metoda se koristi za kombiniranje stabala. Uskoro ćemo vidjeti ovu upotrebu.

3.2. Unesite grafikon od korisnika

Sada trebamo način da od korisnika dobijemo vrhove i bridove grafa i mapiramo ih na objekte koje možemo koristiti u našem algoritmu tijekom izvođenja.

Budući da ćemo koristiti JUnit za testiranje našeg algoritma, ovaj dio ide u @Prije metoda:

@ Prije javne void postavke () {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); } 

Evo, koristili smo Guavinu MutableValueGraph za pohranu našeg grafa. Tada smo koristili ValueGraphBuilder za konstrukciju neusmjerenog ponderiranog grafa.

Metoda putEdgeValue uzima tri argumenta, dva Cijeli brojs za vrhove, a treći Cijeli broj za njegovu težinu, kako je navedeno u MutableValueGraph'S generička deklaracija tipa.

Kao što vidimo, ovo je isti ulaz kao što je prikazano na našem dijagramu od ranije.

3.3. Izvedi stablo s minimalnim rasponom

Konačno, dolazimo do srži stvari, provedbe algoritma.

To ćemo raditi u predavanju koje ćemo nazvati BoruvkaMST. Prvo, proglasimo nekoliko varijabli instance:

javna klasa BoruvkaMST {private static MutableValueGraph mst ​​= ValueGraphBuilder.undirected (). build (); privatni statički int totalWeight; } 

Kao što vidimo, koristimo se MutableValueGraph ovdje da predstavlja MST.

Drugo, definirat ćemo konstruktor, u kojem se događa sva čarolija. Potreban je jedan argument - graf izgradili smo ranije.

Prvo što čini je inicijalizacija a UnionFind vrhova ulaznog grafa. U početku su svi vrhovi njihovi roditelji, svaki s rangom 0:

javni BoruvkaMST (graf MutableValueGraph) {int size = graph.nodes (). size (); UnionFind uf = novi UnionFind (veličina); 

Dalje, stvorit ćemo petlju koja definira broj iteracija potrebnih za stvaranje MST-a - najviše log V puta ili dok nemamo V-1 rubove, gdje je V broj vrhova:

for (int t = 1; t <size && mst.edges (). size () <size - 1; t = t + t) {EndpointPair [] najbližiEdgeArray = novi EndpointPair [veličina]; 

Ovdje također inicijaliziramo niz rubova, najbližiEdgeArray - za pohranu najbližih, manje ponderiranih rubova.

Nakon toga definirat ćemo unutarnju za petlja za iteraciju preko svih rubova grafikona da popuni naš najbližiEdgeArray.

Ako su roditelji dva vrha isti, to je isto stablo i ne dodajemo ga u niz. Inače, uspoređujemo težinu trenutnog ruba s težinom rubova njegovih matičnih vrhova. Ako je manji, tada ga dodajemo najbližiEdgeArray:

za (EndpointPair rub: graph.edges ()) {int u = edge.nodeU (); int v = edge.nodeV (); int uParent = uf.find (u); int vParent = uf.find (v); if (uParent == vParent) {nastavi; } int težina = graph.edgeValueOrDefault (u, v, 0); ako (najbližiEdgeArray [uParent] == ​​null) {najbližiEdgeArray [uParent] = rub; } ako (najbližiEdgeArray [vParent] == ​​null) {najbližiEdgeArray [vParent] = rub; } int uParentWeight = graph.edgeValueOrDefault (najbližiEdgeArray [uParent] .nodeU (), najbližiEdgeArray [uParent] .nodeV (), 0); int vParentWeight = graph.edgeValueOrDefault (najbližiEdgeArray [vParent] .nodeU (), najbližiEdgeArray [vParent] .nodeV (), 0); if (težina <uParentWeight) {najbližiEdgeArray [uParent] = rub; } if (težina <vParentWeight) {najbližiEdgeArray [vParent] = rub; }} 

Zatim ćemo definirati drugu unutarnju petlju za stvaranje stabla. Na ovo ćemo stablo dodati rubove iz gornjeg koraka, a da isti rub ne dodamo dva puta. Uz to ćemo izvesti i unija na naš UnionFind izvesti i pohraniti roditelje i redove vrhova novostvorenih stabala:

for (int i = 0; i <size; i ++) {EndpointPair edge = najbližiEdgeArray [i]; if (rub! = null) {int u = edge.nodeU (); int v = edge.nodeV (); int težina = graph.edgeValueOrDefault (u, v, 0); if (uf.find (u)! = uf.find (v)) {mst.putEdgeValue (u, v, težina); ukupna težina + = težina; uf.union (u, v); }}} 

Nakon ponavljanja ovih koraka najviše V puta ili dok ne dobijemo V-1 rubove, rezultirajuće stablo je naš MST.

4. Ispitivanje

Na kraju, pogledajmo jednostavan JUnit za provjeru naše implementacije:

@Test javna praznina givenInputGraph_whenBoruvkaPerformed_thenMinimumSpanningTree () {BoruvkaMST boruvkaMST = nova BoruvkaMST (graf); Promjenjiva vrijednostGraph mst ​​= boruvkaMST.getMST (); assertEquals (30, boruvkaMST.getTotalWeight ()); assertEquals (4, mst.getEdgeCount ()); } 

Kao što vidimo, dobili smo MST s težinom od 30 i 4 ruba, isto kao i slikovni primjer.

5. Zaključak

U ovom uputstvu vidjeli smo implementaciju Java algoritma Boruvka. Njegova vremenska složenost je O (E log V), gdje je E broj bridova, a V broj vrhova.

Kao i uvijek, izvorni kod dostupan je na GitHub-u.