streamalism.org

1. Oversigt

I denne vejledning vi kigger på Java-implementeringen af ​​Boruvkas algoritme til at finde et Minimum Spanning Tree (MST) i en kantvægtet graf.

Det går forud for Prims og Kruskals algoritmer, men kan stadig betragtes som et kryds mellem de to.

2. Boruvkas algoritme

Vi hopper lige ind i algoritmen ved hånden. Lad os se på en smule historie og derefter algoritmen selv.

2.1. Historie

En måde at finde en MST på en given graf blev først formuleret af Otakar Boruvka i 1926. Dette var langt før computere overhovedet eksisterede, og var faktisk modelleret til at designe et effektivt el-distributionssystem.

Georges Sollin genopdagede det i 1965 og brugte det i parallel computing.

2.2. Algoritmen

Den centrale idé med algoritmen er at starte med en flok træer, hvor hvert toppunkt repræsenterer et isoleret træ. Derefter skal vi fortsætte med at tilføje kanter for at reducere antallet af isolerede træer, indtil vi har et enkelt tilsluttet træ.

Lad os se dette i trin med et eksempel på en graf:

• Trin 0: Opret en graf
• Trin 1: Start med en flok ikke-tilsluttede træer (antal træer = antal hjørner)
• Trin 2: mens der er ikke-tilsluttede træer, for hvert ikke-tilsluttede træ:
  • find sin kant med mindre vægt
  • tilføj denne kant for at forbinde et andet træ

3. Java-implementering

Lad os nu se, hvordan vi kan implementere dette i Java.

3.1. Det UnionFind Datastruktur

Til at begynde med, vi har brug for en datastruktur til at gemme forældrene og rækken af ​​vores hjørner.

Lad os definere en klasse UnionFind til dette formål med to metoder: Unionog finde:

offentlig klasse UnionFind {private int [] forældre; private int [] rækker; offentlig UnionFind (int n) {forældre = ny int [n]; rangerer = ny int [n]; for (int i = 0; i <n; i ++) {forældre [i] = i; rækker [i] = 0; }} offentlig int finde (int u) {mens (u! = forældre [u]) {u = forældre [u]; } returner dig; } offentlig tomrumsforening (int u, int v) {int uParent = find (u); int vParent = find (v); hvis (uParent == vParent) {return; } hvis (rangerer [uParent] rangerer [vParent]) {forældre [vParent] = uParent; } andet {forældre [vParent] = uParent; rangerer [uParent] ++; }}} 

Vi kan tænke på denne klasse som en hjælperstruktur til at opretholde forholdet mellem vores hjørner og gradvist opbygge vores MST.

At finde ud af om to hjørner u og v hører til det samme træ, vi ser, om find (u) returnerer den samme forælder som find (v). Det Union metoden bruges til at kombinere træer. Vi ser denne brug snart.

3.2. Indtast en graf fra brugeren

Nu har vi brug for en måde at få grafens hjørner og kanter fra brugeren og kortlægge dem til objekter, vi kan bruge i vores algoritme ved kørsel.

Da vi bruger JUnit til at teste vores algoritme, går denne del i en @Før metode:

@Før offentlig ugyldig opsætning () {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 brugt guavas MutableValueGraph for at gemme vores graf. Så brugte vi ValueGraphBuilder at konstruere en ikke-rettet vægtet graf.

Metoden putEdgeValue tager tre argumenter, to Heltals for hjørnerne og den tredje Heltal for dens vægt, som specificeret af MutableValueGraph'S generiske typedeklaration.

Som vi kan se, er dette den samme input som vist i vores diagram fra tidligere.

3.3. Hent minimum spændende træ

Endelig kommer vi til kernen i sagen, implementeringen af ​​algoritmen.

Vi gør dette i en klasse, vi ringer til BoruvkaMST. Lad os først erklære et par instansvariabler:

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

Som vi kan se, bruger vi MutableValueGraph her for at repræsentere MST.

For det andet definerer vi en konstruktør, hvor al magien sker. Det kræver et argument - kurve vi byggede tidligere.

Den første ting det gør er at initialisere en UnionFind af indgangsgrafens hjørner. Oprindeligt er alle hjørner deres egne forældre, hver med en rang på 0:

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

Dernæst opretter vi en sløjfe, der definerer antallet af iterationer, der kræves for at oprette MST - højst log V-gange eller indtil vi har V-1-kanter, hvor V er antallet af hjørner:

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

Her initialiserer vi også en række kanter, tættestEdgeArray - for at gemme de nærmeste, mindre vægtede kanter.

Derefter definerer vi et indre til loop for at gentage over alle kanterne på grafen for at udfylde vores tættestEdgeArray.

Hvis forældrene til de to hjørner er ens, er det det samme træ, og vi føjer det ikke til arrayet. Ellers sammenligner vi den aktuelle kantvægt med vægten af ​​de overordnede hjørneres kanter. Hvis det er mindre, tilføjer 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) {fortsæt; } int vægt = 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ærmesteEdgeArray [uParent] .nodeU (), nærmesteEdgeArray [uParent] .nodeV (), 0); int vParentWeight = graph.edgeValueOrDefault (nærmesteEdgeArray [vParent] .nodeU (), nærmesteEdgeArray [vParent] .nodeV (), 0); hvis (vægt <uParentWeight) {nærmestEdgeArray [uParent] = kant; } hvis (vægt <vParentWeight) {nærmestEdgeArray [vParent] = kant; }} 

Derefter definerer vi en anden indre sløjfe for at oprette et træ. Vi tilføjer kanter fra ovenstående trin til dette træ uden at tilføje den samme kant to gange. Derudover udfører vi en Union på vores UnionFind at udlede og gemme forældre og rækker af de nyoprettede træers hjørner:

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 vægt = graph.edgeValueOrDefault (u, v, 0); hvis (uf.find (u)! = uf.find (v)) {mst.putEdgeValue (u, v, vægt); totalVægt + = vægt; uf.union (u, v); }}} 

Efter at have gentaget disse trin højst log V-tider eller indtil vi har V-1-kanter, er det resulterende træ vores MST.

4. Testning

Lad os endelig se en simpel JUnit til at verificere vores implementering:

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

Som vi kan se, fik vi MST med en vægt på 30 og 4 kanter, det samme som billedeksemplet.

5. Konklusion

I denne vejledning så vi Java-implementeringen af ​​Boruvka-algoritmen. Dens tidskompleksitet er O (E log V), hvor E er antallet af kanter, og V er antallet af hjørner.

Som altid er kildekoden tilgængelig på GitHub.