streamalism.org

1. Áttekintés

Ebben az oktatóanyagban megnézzük a Boruvka algoritmusának Java implementációját egy éllel súlyozott gráf Minimum Spanning Tree (MST) megkeresésére..

Korábbi a Prim és Kruskal algoritmusoknál, de mégis a kettő keresztezésének tekinthető.

2. Boruvka algoritmusa

Ugrunk közvetlenül a kéznél lévő algoritmusba. Nézzünk meg egy kis előzményt, majd magát az algoritmust.

2.1. Történelem

Otakar Boruvka 1926-ban fogalmazta meg először az adott grafikon MST-jének megtalálásának módját. Ez még azelőtt történt, hogy a számítógépek még léteztek volna, és valójában egy hatékony villamosenergia-elosztó rendszer megtervezésére készült.

Georges Sollin 1965-ben fedezte fel újra és párhuzamosan használta.

2.2. Az algoritmus

Az algoritmus központi gondolata az, hogy egy csomó fával kell kezdeni, amelyek mindegyik csúcsa egy elszigetelt fát képvisel. Ezután folytatnunk kell az élek hozzáadását az elszigetelt fák számának csökkentése érdekében, amíg egyetlen összekapcsolt fa nem lesz.

Lássuk ezt lépésenként egy példa grafikon segítségével:

• 0. lépés: Hozzon létre egy grafikont
• 1. lépés: Kezdjen egy csomó nem kapcsolódó fával (fák száma = csúcsok száma)
• 2. lépés: amíg vannak nem kapcsolódó fák, minden egyes nem kapcsolódó fához:
  • kisebb súllyal találja meg az élét
  • adja hozzá ezt az élt egy másik fa összekapcsolásához

3. Java implementáció

Most nézzük meg, hogyan tudjuk ezt megvalósítani a Java-ban.

3.1. A UnionFind Adatszerkezet

Először is, szükségünk van egy adatstruktúrára a csúcsaink szüleinek és sorainak tárolásához.

Határozzunk meg egy osztályt UnionFind erre a célra, két módszerrel: unió, és megtalálja:

public class UnionFind {private int [] szülők; magánintézmény [] rangsorol; public UnionFind (int n) {szülők = new int [n]; rangok = új int [n]; mert (int i = 0; i <n; i ++) {szülők [i] = i; rangsorok [i] = 0; }} public int find (int u) {while (u! = szülők [u]) {u = szülők [u]; } return u; } public void union (int u, int v) {int uParent = megtalálni (u); int vParent = megtalálás (v); if (uParent == vParent) {return; } if (rangsorolja [uParent] rangsorolja [vParent]) {szülők [vParent] = uParent; } else {szülők [vParent] = uParent; rangsorol [uParent] ++; }}} 

Úgy gondolhatjuk, hogy ez az osztály segítő struktúra a csúcsaink közötti kapcsolatok fenntartásában és az MST fokozatos kiépítésében.

Utána járni hogy két csúcs u és v ugyanahhoz a fához tartoznak, meglátjuk, hogy megtalálni (u) ugyanazzal a szülővel tér vissza, mint megtalálás (v). A unió módszert alkalmazzák a fák kombinálására. Rövidesen meglátjuk ezt a felhasználást.

3.2. Adjon meg egy grafikont a felhasználótól

Most arra van szükségünk, hogy megszerezzük a grafikon csúcsait és éleit a felhasználótól, és azokat olyan objektumokhoz hozzárendeljük, amelyeket futás közben használhatunk algoritmusunkban.

Mivel a JUnit-et fogjuk használni algoritmusunk tesztelésére, ez a rész a @Előtt módszer:

@A nyilvános void beállítása előtt () {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); } 

Itt Guava-okat használtunk MutableValueGraph hogy tároljuk a grafikonunkat. Akkor használtuk ValueGraphBuilder irányítatlan súlyozott gráf létrehozásához.

A módszer, a metódus putEdgeValue három érvet vesz fel, kettőt Egész száms a csúcsokra, a harmadik pedig Egész szám súlyának megfelelően, a MutableValueGraph’S általános típusú nyilatkozata.

Mint láthatjuk, ez ugyanaz a bemenet, mint az előző diagramunkban látható.

3.3. Vezesse le a minimális fát

Végül eljutottunk a kérdés lényegéhez, az algoritmus megvalósításához.

Ezt egy olyan osztályban fogjuk megtenni, amelyet felhívunk BoruvkaMST. Először deklaráljunk pár példányváltozót:

nyilvános osztály BoruvkaMST {privát statikus MutableValueGraph mst ​​= ValueGraphBuilder.undirected (). build (); privát statikus int totalWeight; } 

Mint láthatjuk, használjuk MutableValueGraph itt képviselni az MST-t.

Másodszor meghatározunk egy konstruktort, ahol minden varázslat megtörténik. Egy érvre van szükség - a grafikon korábban építettük.

Az első dolog az, hogy inicializálja a UnionFind a bemenő gráf csúcsainak. Kezdetben minden csúcs a saját szülője, mindegyik 0-s ranggal rendelkezik:

public BoruvkaMST (MutableValueGraph graph) {int size = graph.nodes (). size (); UnionFind uf = new UnionFind (méret); 

Ezután létrehozunk egy hurkot, amely meghatározza az MST létrehozásához szükséges iterációk számát - legfeljebb log V-időkig, vagy amíg V-1 élek nem lesznek, ahol V a csúcsok száma:

mert (int t = 1; t <méret && mst.szegélyek (). méret () <méret - 1; t = t + t) {EndpointPair [] legközelebbEdgeArray = új EndpointPair [méret]; 

Itt egy éltömböt is inicializálunk, legközelebbEdgeArray - a legközelebbi, kevésbé súlyozott élek tárolására.

Ezután meghatározunk egy belső elemet mert hurok, hogy a grafikon minden széle felett iteráljon, hogy feltöltse a legközelebbEdgeArray.

Ha a két csúcs szülője azonos, akkor ez ugyanaz a fa, és nem adjuk hozzá a tömbhöz. Ellenkező esetben összehasonlítjuk az aktuális él súlyát a szülőcsúcsok éleinek súlyával. Ha kisebb, akkor hozzáadjuk legközelebbiEdgeArray:

for (EndpointPair él: graph.edges ()) {int u = edge.nodeU (); int v = él.csomópont V (); int uParent = uf.find (u); int vParent = uf.find (v); ha (uParent == vParent) {folytatás; } int súly = graph.edgeValueOrDefault (u, v, 0); if (legközelebbEdgeArray [uParent] == ​​null) {legközelebbEdgeArray [uParent] = él; } if (legközelebbEdgeArray [vParent] == ​​null) {legközelebbEdgeArray [vParent] = él; } int uParentWeight = graph.edgeValueOrDefault (artimebbEdgeArray [uParent] .nodeU (), legközelebbEdgeArray [uParent] .nodeV (), 0); int vParentWeight = graph.edgeValueOrDefault (legközelebbEdgeArray [vParent] .nodeU (), legközelebbEdgeArray [vParent] .nodeV (), 0); if (súly <uParentWeight) {legközelebbEdgeArray [uParent] = él; } if (súly <vParentWeight) {legközelebb EdgeArray [vParent] = él; }} 

Ezután meghatározunk egy második belső hurkot egy fa létrehozásához. A fenti lépésből származó éleket hozzáadjuk ehhez a fához anélkül, hogy ugyanazt az élt kétszer adnánk hozzá. Ezenkívül elvégezzük a unió miénken UnionFind levezetni és tárolni az újonnan létrehozott fák csúcsainak szüleit és rangjait:

for (int i = 0; i <méret; i ++) {EndpointPair él = legközelebbEdgeArray [i]; if (él! = null) {int u = él.csomópontU (); int v = él.csomópont V (); int súly = graph.edgeValueOrDefault (u, v, 0); if (uf.find (u)! = uf.find (v)) {mst.putEdgeValue (u, v, súly); totalWeight + = súly; uf.union (u, v); }}} 

Miután megismételte ezeket a lépéseket legfeljebb log V alkalommal, vagy amíg nem rendelkezünk V-1 élekkel, az eredményül kapott fa az MST.

4. Tesztelés

Végül nézzünk meg egy egyszerű JUnit-t a megvalósításunk ellenőrzéséhez:

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

Mint láthatjuk, megvan a MST súlya 30 és 4 él, ugyanaz, mint a képi példa.

5. Következtetés

Ebben az oktatóanyagban a Boruvka algoritmus Java implementációját láthattuk. Időkomplexuma O (E log V), ahol E az élek száma és V a csúcsok száma.

Mint mindig, a forráskód is elérhető a GitHubon.