streamalism.org

1. Oversikt

I denne veiledningen, vi tar en titt på Java-implementeringen av Boruvkas algoritme for å finne et Minimum Spanning Tree (MST) av en kantvektet graf.

Det går foran Prim og Kruskals algoritmer, men kan fremdeles betraktes som et kryss mellom de to.

2. Boruvkas algoritme

Vi hopper rett inn i algoritmen for hånden. La oss se på litt historie og deretter selve algoritmen.

2.1. Historie

En måte å finne en MST av en gitt graf ble først formulert av Otakar Boruvka i 1926. Dette var langt før datamaskiner eksisterte, og ble faktisk modellert for å utforme et effektivt strømfordelingssystem.

Georges Sollin gjenoppdaget den i 1965 og brukte den i parallell databehandling.

2.2. Algoritmen

Den sentrale ideen med algoritmen er å starte med en haug med trær hvor hvert toppunkt representerer et isolert tre. Deretter må vi fortsette å legge til kanter for å redusere antall isolerte trær til vi har et enkelt sammenhengende tre.

La oss se dette i trinn med et eksempel på en graf:

• Trinn 0: Lag en graf
• Trinn 1: Start med en haug med ikke-tilkoblede trær (antall trær = antall hjørner)
• Trinn 2: mens det er frakoblede trær, for hvert frakoblet tre:
  • finn kanten med mindre vekt
  • legg til denne kanten for å koble til et annet tre

3. Java-implementering

La oss nå se hvordan vi kan implementere dette i Java.

3.1. De UnionFind Data struktur

Til å begynne med, vi trenger en datastruktur for å lagre foreldrene og rekkene til toppunktene våre.

La oss definere en klasse UnionFind for dette formålet, med to metoder: fagforening, og finne:

offentlig klasse UnionFind {private int [] foreldre; private int [] rekker; offentlig UnionFind (int n) {foreldre = ny int [n]; rangerer = ny int [n]; for (int i = 0; i <n; i ++) {foreldre [i] = i; rangerer [i] = 0; }} offentlig int finne (int u) {mens (u! = foreldre [u]) {u = foreldre [u]; } returner deg; } offentlig ugyldig forening (int u, int v) {int uParent = finn (u); int vParent = finn (v); hvis (uParent == vParent) {return; } hvis (rangerer [uParent] rangerer [vParent]) {foreldre [vParent] = uParent; } annet {foreldre [vParent] = uParent; rangerer [uParent] ++; }}} 

Vi kan tenke på denne klassen som en hjelperstruktur for å opprettholde forhold mellom hjørnene våre og gradvis bygge opp vår MST.

Å finne ut om det er to hjørner u og v tilhører samme tre, vi ser om finn (u) returnerer samme forelder som finn (v). De fagforening metoden brukes til å kombinere trær. Vi ser denne bruken snart.

3.2. Skriv inn en graf fra brukeren

Nå trenger vi en måte å få grafens hjørner og kanter fra brukeren og kartlegge dem til objekter vi kan bruke i algoritmen vår ved kjøretid.

Siden vi bruker JUnit for å teste ut algoritmen vår, går denne delen i en @Før metode:

@Før offentlig ugyldig oppsett () {graf = 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); } 

Her har vi brukt Guava MutableValueGraph for å lagre grafen vår. Så brukte vi ValueGraphBuilder å konstruere en ikke-rettet vektet graf.

Metoden putEdgeValue tar tre argumenter, to Heltalls for toppunktene, og den tredje Heltall for sin vekt, som spesifisert av MutableValueGraph’S generiske typedeklarasjon.

Som vi kan se, er dette samme inngang som vist i diagrammet vårt fra tidligere.

3.3. Derive Minimum Spanning Tree

Til slutt kommer vi til kjernen i saken, implementeringen av algoritmen.

Vi gjør dette i en klasse vi vil ringe BoruvkaMST. La oss først erklære et par eksempler på variabler:

offentlig klasse BoruvkaMST {privat statisk MutableValueGraph mst ​​= ValueGraphBuilder.undirected (). build (); privat statisk int totalvekt; } 

Som vi ser, bruker vi det MutableValueGraph her for å representere MST.

For det andre vil vi definere en konstruktør, der all magien skjer. Det krever ett argument - kurve vi bygde tidligere.

Det første den gjør er å initialisere en UnionFind av inngangsgrafens toppunkt. Opprinnelig er alle toppunktene sine egne foreldre, hver med rangering 0:

offentlig BoruvkaMST (MutableValueGraph-graf) {int size = graph.nodes (). size (); UnionFind uf = ny UnionFind (størrelse); 

Deretter oppretter vi en sløyfe som definerer antall iterasjoner som kreves for å lage MST - på det meste logg V ganger eller til vi har V-1 kanter, hvor V er antall hjørner:

for (int t = 1; t <størrelse && mst.edges (). størrelse () <størrelse - 1; t = t + t) {EndpointPair [] nærmesteEdgeArray = ny EndpointPair [størrelse]; 

Her initialiserer vi også en rekke kanter, nærmestEdgeArray - for å lagre de nærmeste, mindre vektede kantene.

Etter det vil vi definere en indre til løkke for å gjenta over alle kantene av grafen for å fylle ut vår nærmestEdgeArray.

Hvis foreldrene til de to toppunktene er de samme, er det samme tre, og vi legger det ikke til matrisen. Ellers sammenligner vi gjeldende kantvekt med vekten av foreldrekantenes kanter. Hvis det er mindre, så legger vi det til nærmesteEdgeArray:

for (EndpointPair edge: graph.edges ()) {int u = edge.nodeU (); int v = edge.nodeV (); int uParent = uf.find (u); int vParent = uf.find (v); hvis (uParent == vParent) {fortsett; } int vekt = graph.edgeValueOrDefault (u, v, 0); hvis (nærmestEdgeArray [uParent] == ​​null) {nærmestEdgeArray [uParent] = kant; } hvis (nærmesteEdgeArray [vParent] == ​​null) {nærmesteEdgeArray [vParent] = kant; } int uParentWeight = graph.edgeValueOrDefault (nærmestEdgeArray [uParent] .nodeU (), nærmestEdgeArray [uParent] .nodeV (), 0); int vParentWeight = graph.edgeValueOrDefault (nærmesteEdgeArray [vParent] .nodeU (), nærmesteEdgeArray [vParent] .nodeV (), 0); hvis (vekt <uParentWeight) {nærmestEdgeArray [uParent] = kant; } hvis (vekt <vParentWeight) {nærmestEdgeArray [vParent] = kant; }} 

Deretter definerer vi en andre indre sløyfe for å lage et tre. Vi legger til kanter fra trinnet ovenfor til dette treet uten å legge til den samme kanten to ganger. I tillegg vil vi utføre en fagforening på vår UnionFind å utlede og lagre foreldre og rekker av de nyopprettede trærnes toppunkt:

for (int i = 0; i <størrelse; i ++) {EndpointPair edge = nærmestEdgeArray [i]; hvis (edge! = null) {int u = edge.nodeU (); int v = edge.nodeV (); int vekt = graph.edgeValueOrDefault (u, v, 0); hvis (uf.find (u)! = uf.find (v)) {mst.putEdgeValue (u, v, weight); totalvekt + = vekt; uf.union (u, v); }}} 

Etter å ha gjentatt disse trinnene på det meste logger V ganger eller til vi har V-1 kanter, er det resulterende treet vår MST.

4. Testing

Til slutt, la oss se en enkel JUnit for å bekrefte implementeringen vår:

@Test offentlig tomrom gittInputGraph_whenBoruvkaPerformed_thenMinimumSpanningTree () {BoruvkaMST boruvkaMST = ny BoruvkaMST (graf); MutableValueGraph mst ​​= boruvkaMST.getMST (); assertEquals (30, boruvkaMST.getTotalWeight ()); assertEquals (4, mst.getEdgeCount ()); } 

Som vi kan se, fikk vi MST med en vekt på 30 og 4 kanter, det samme som billedeksemplet.

5. Konklusjon

I denne opplæringen så vi Java-implementeringen av Boruvka-algoritmen. Dens tidskompleksitet er O (E log V), hvor E er antall kanter og V er antall hjørner.

Som alltid er kildekoden tilgjengelig på GitHub.