Boruvka's algoritme voor minimale overspanning van bomen in Java

1. Overzicht

In deze tutorial we zullen de Java-implementatie van Boruvka's algoritme bekijken voor het vinden van een Minimum Spanning Tree (MST) van een randgewogen grafiek.

Het dateert van vóór de algoritmen van Prim en Kruskal, maar kan nog steeds worden beschouwd als een kruising tussen de twee.

2. Boruvka's algoritme

We springen meteen in het huidige algoritme. Laten we een stukje geschiedenis bekijken en dan het algoritme zelf.

2.1. Geschiedenis

Een manier om een ​​MST van een bepaalde grafiek te vinden, werd voor het eerst geformuleerd door Otakar Boruvka in 1926. Dit was lang voordat computers bestonden, en werd in feite gemodelleerd om een ​​efficiënt elektriciteitsdistributiesysteem te ontwerpen.

Georges Sollin herontdekte het in 1965 en gebruikte het bij parallel computergebruik.

2.2. Het algoritme

Het centrale idee van het algoritme is om te beginnen met een aantal bomen, waarbij elk hoekpunt een geïsoleerde boom vertegenwoordigt. Vervolgens moeten we randen blijven toevoegen om het aantal geïsoleerde bomen te verminderen totdat we een enkele verbonden boom hebben.

Laten we dit in stappen bekijken met een voorbeeldgrafiek:

  • Stap 0: maak een grafiek
  • Stap 1: begin met een aantal niet-verbonden bomen (aantal bomen = aantal hoekpunten)
  • Stap 2: terwijl er niet-verbonden bomen zijn, voor elke niet-verbonden boom:
    • vind zijn voorsprong met minder gewicht
    • voeg deze rand toe om een ​​andere boom te verbinden

3. Java-implementatie

Laten we nu eens kijken hoe we dit in Java kunnen implementeren.

3.1. De UnionFind Data structuur

Om te beginnen met, we hebben een datastructuur nodig om de ouders en rangen van onze hoekpunten op te slaan.

Laten we een klasse definiëren UnionFind voor dit doel, met twee methoden: unie, en vind:

openbare klasse UnionFind {private int [] ouders; private int [] rangen; openbare UnionFind (int n) {ouders = nieuwe int [n]; rangen = nieuwe int [n]; voor (int i = 0; i <n; i ++) {ouders [i] = i; rangen [i] = 0; }} public int find (int u) {while (u! = ouders [u]) {u = ouders [u]; } retourneer u; } public void union (int u, int v) {int uParent = find (u); int vParent = vind (v); if (uParent == vParent) {return; } if (rangschikt [uParent] rangschikt [vParent]) {ouders [vParent] = uParent; } anders {ouders [vParent] = uParent; rangschikt [uParent] ++; }}} 

We kunnen deze klasse beschouwen als een hulpstructuur voor het onderhouden van relaties tussen onze hoekpunten en het geleidelijk opbouwen van onze MST.

Er achter komen of twee hoekpunten u en v behoren tot dezelfde boom, we zien of vind (u) geeft dezelfde ouder terug als vind (v). De unie methode wordt gebruikt om bomen te combineren. We zullen dit gebruik binnenkort zien.

3.2. Voer een grafiek van de gebruiker in

Nu hebben we een manier nodig om de hoekpunten en randen van een grafiek van de gebruiker te krijgen en deze toe te wijzen aan objecten die we tijdens runtime in ons algoritme kunnen gebruiken.

Omdat we JUnit zullen gebruiken om ons algoritme te testen, gaat dit deel in een @Voordat methode:

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

Hier hebben we Guava's gebruikt MutableValueGraph om onze grafiek op te slaan. Toen gebruikten we ValueGraphBuilder om een ​​ongerichte gewogen grafiek te construeren.

De methode putEdgeValue heeft drie argumenten, twee Geheel getals voor de hoekpunten, en de derde Geheel getal voor zijn gewicht, zoals gespecificeerd door MutableValueGraph'S algemene typeverklaring.

Zoals we kunnen zien, is dit dezelfde invoer als in ons diagram van eerder.

3.3. Leid een minimale overspanningsboom af

Ten slotte komen we bij de kern van de zaak, de implementatie van het algoritme.

We doen dit in een klas die we zullen bellen BoruvkaMST. Laten we eerst een aantal instantievariabelen declareren:

openbare klasse BoruvkaMST {privé statisch MutableValueGraph mst ​​= ValueGraphBuilder.undirected (). build (); privé statisch int totaalgewicht; } 

Zoals we kunnen zien, maken we er gebruik van MutableValueGraph hier om de MST te vertegenwoordigen.

Ten tweede zullen we een constructor definiëren, waar alle magie plaatsvindt. Er is één argument voor nodig - de grafiek we hebben eerder gebouwd.

Het eerste dat het doet, is een UnionFind van de hoekpunten van de invoergrafiek. Aanvankelijk zijn alle hoekpunten hun eigen ouders, elk met een rangorde van 0:

openbare BoruvkaMST (MutableValueGraph-grafiek) {int size = graph.nodes (). size (); UnionFind uf = nieuwe UnionFind (grootte); 

Vervolgens maken we een lus die het aantal iteraties definieert dat nodig is om de MST te maken - maximaal log V keer of totdat we V-1 randen hebben, waarbij V het aantal hoekpunten is:

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

Hier initialiseren we ook een reeks randen, dichtstbijzijndeEdgeArray - om de dichtstbijzijnde, minder gewogen randen op te slaan.

Daarna zullen we een innerlijk definiëren voor loop om alle randen van de grafiek te herhalen om onze dichtstbijzijndeEdgeArray.

Als de ouders van de twee hoekpunten hetzelfde zijn, is het dezelfde boom en voegen we deze niet toe aan de array. Anders vergelijken we het gewicht van de huidige rand met het gewicht van de bovenliggende hoekpunten. Als het minder is, voegen we het toe aan dichtstbijzijndeEdgeArray:

voor (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) {ga verder; } int gewicht = graph.edgeValueOrDefault (u, v, 0); if (dichtstbijzijndeEdgeArray [uParent] == ​​null) {dichtstbijzijndeEdgeArray [uParent] = edge; } if (dichtstbijzijndeEdgeArray [vParent] == ​​null) {dichtstbijzijndeEdgeArray [vParent] = edge; } int uParentWeight = graph.edgeValueOrDefault (dichtstbijzijndeEdgeArray [uParent] .nodeU (), dichtstbijzijndeEdgeArray [uParent] .nodeV (), 0); int vParentWeight = graph.edgeValueOrDefault (dichtstbijzijndeEdgeArray [vParent] .nodeU (), dichtstbijzijndeEdgeArray [vParent] .nodeV (), 0); if (gewicht <uParentWeight) {dichtstbijzijndeEdgeArray [uParent] = edge; } if (gewicht <vParentWeight) {dichtstbijzijndeEdgeArray [vParent] = edge; }} 

Vervolgens definiëren we een tweede binnenste lus om een ​​boom te maken. We voegen randen van de bovenstaande stap toe aan deze boom zonder dezelfde rand twee keer toe te voegen. Daarnaast voeren we een unie op onze UnionFind om ouders en rangen van de nieuw gecreëerde hoekpunten van de bomen af ​​te leiden en op te slaan:

for (int i = 0; i <size; i ++) {EndpointPair edge = dichtstbijzijndeEdgeArray [i]; if (edge! = null) {int u = edge.nodeU (); int v = edge.nodeV (); int gewicht = graph.edgeValueOrDefault (u, v, 0); if (uf.find (u)! = uf.find (v)) {mst.putEdgeValue (u, v, gewicht); totaalgewicht + = gewicht; uf.union (u, v); }}} 

Na het herhalen van deze stappen maximaal log V keer of totdat we V-1 randen hebben, is de resulterende boom onze MST.

4. Testen

Laten we tot slot een eenvoudige JUnit bekijken om onze implementatie te verifiëren:

@Test openbare leegte gegevenInputGraph_whenBoruvkaPerformed_thenMinimumSpanningTree () {BoruvkaMST boruvkaMST = nieuwe BoruvkaMST (grafiek); MutableValueGraph mst ​​= boruvkaMST.getMST (); assertEquals (30, boruvkaMST.getTotalWeight ()); assertEquals (4, mst.getEdgeCount ()); } 

Zoals we kunnen zien, hebben we de MST met een gewicht van 30 en 4 randen, hetzelfde als het geïllustreerde voorbeeld.

5. Conclusie

In deze tutorial hebben we de Java-implementatie van het Boruvka-algoritme gezien. De tijdcomplexiteit is O (E log V), waarbij E het aantal randen is en V het aantal hoekpunten.

Zoals altijd is de broncode beschikbaar op GitHub.