Bredde-første søgealgoritme i Java
1. Oversigt
I denne vejledning lærer vi om Breadth-First Search-algoritmen, som giver os mulighed for at søge efter en node i et træ eller en graf ved at rejse gennem deres noder bredde-først i stedet for dybde-først.
Først gennemgår vi en smule teori om denne algoritme til træer og grafer. Derefter dykker vi ned i implementeringerne af algoritmerne i Java. Endelig dækker vi deres tidskompleksitet.
2. Algoritme for bredde-første søgning
Den grundlæggende tilgang til algoritmen Breadth-First Search (BFS) er at søge efter en knude i et træ eller en grafstruktur ved at udforske naboer før børn.
Først ser vi, hvordan denne algoritme fungerer for træer. Derefter tilpasser vi det til grafer, som har den specifikke begrænsning til undertiden at indeholde cyklusser. Endelig vil vi diskutere ydeevnen for denne algoritme.
2.1. Træer
Ideen bag BFS-algoritmen for træer er at opretholde en kø med noder, der vil sikre rækkefølgen af traversal. I begyndelsen af algoritmen indeholder køen kun rodnoden. Vi gentager disse trin, så længe køen stadig indeholder en eller flere noder:
- Pop den første knude fra køen
- Hvis den knude er den, vi søger efter, er søgningen slut
- Ellers tilføj børnene til denne node til slutningen af køen og gentag trinene
Afslutning af udførelsen sikres ved fravær af cykler. Vi ser, hvordan du styrer cyklusser i det næste afsnit.
2.2. Grafer
I tilfælde af grafer skal vi tænke på mulige cyklusser i strukturen. Hvis vi blot anvender den tidligere algoritme på en graf med en cyklus, løber den for evigt. Derfor, vi bliver nødt til at opbevare en samling af de besøgte noder og sikre, at vi ikke besøger dem to gange:
- Pop den første knude fra køen
- Kontroller, om knudepunktet allerede er besøgt, hvis det er tilfældet
- Hvis den knude er den, vi søger efter, er søgningen slut
- Ellers skal du føje det til de besøgte noder
- Føj børnene til denne node til køen, og gentag disse trin
3. Implementering i Java
Nu hvor teorien er blevet dækket, lad os få vores hænder i koden og implementere disse algoritmer i Java!
3.1. Træer
Først implementerer vi træalgoritmen. Lad os designe vores Træ klasse, som består af en værdi og børn repræsenteret af en liste over andre Træs:
public class Tree {privat T-værdi; privat liste børn; privat træ (T-værdi) {this.value = værdi; this.children = ny ArrayList (); } offentligt statisk træ af (T-værdi) {returner nyt træ (værdi); } offentligt træ addChild (T værdi) {Tree newChild = nyt træ (værdi); children.add (newChild); returner newChild; }} For at undgå at skabe cyklusser oprettes børn af selve klassen baseret på en given værdi.
Lad os derefter give en Søg() metode:
offentlig statisk Valgfri søgning (T-værdi, trærod) {// ...} Som vi nævnte tidligere, BFS-algoritmen bruger en kø til at krydse noderne. Først og fremmest tilføjer vi vores rod knude til denne kø:
Kø kø = ny ArrayDeque (); kø.tillæg (rod); Derefter er vi nødt til at løkke, mens køen ikke er tom, og hver gang vi springer en node ud fra køen:
mens (! queue.isEmpty ()) {Tree currentNode = queue.remove (); }Hvis den knude er den, vi søger efter, returnerer vi den, ellers tilføjer vi dens børn til køen:
hvis (currentNode.getValue (). er lig med (værdi)) {return Optional.of (currentNode); } andet {queue.addAll (currentNode.getChildren ()); }Endelig, hvis vi besøgte alle knudepunkter uden at finde den, vi søgte efter, returnerer vi et tomt resultat:
returnere Optional.empty ();Lad os forestille os et eksempel på en træstruktur:
Hvilket oversættes til Java-koden:
Tree root = Tree.of (10); Tree rootFirstChild = root.addChild (2); Tree depthMostChild = rootFirstChild.addChild (3); Tree rootSecondChild = root.addChild (4);Derefter, hvis vi søger efter værdien 4, forventer vi, at algoritmen krydser noder med værdierne 10, 2 og 4 i den rækkefølge:
BreadthFirstSearchAlgorithm.search (4, rod)Vi kan verificere det ved at logge værdien af de besøgte noder:
[main] INFO c.b.a.b.BreadthFirstSearchAlgorithm - Besøgt node med værdi: 10 [main] INFO c.b.a.b.BreadthFirstSearchAlgorithm - Besøgt node med værdi: 2 [main] INFO c.b.a.b.BreadthFirstSearchAlgorithm - Besøgt node med værdi: 43.2. Grafer
Det afslutter tilfældet med træer. Lad os nu se, hvordan vi skal håndtere grafer. I modsætning til træer kan grafer indeholde cyklusser. Det betyder, som vi har set i det foregående afsnit, vi er nødt til at huske de noder, vi besøgte for at undgå en uendelig løkke. Vi ser om et øjeblik, hvordan vi opdaterer algoritmen for at overveje dette problem, men lad os først definere vores grafstruktur:
offentlig klasse Node {privat T-værdi; privat sæt naboer; offentlig knude (T-værdi) {this.value = værdi; this.neighbors = nye HashSet (); } public void connect (Node node) {if (this == node) throw new IllegalArgumentException ("Kan ikke forbinde node til sig selv"); this.neighbors.add (node); node.neighbors.add (dette); }} Nu kan vi se, i modsætning til træer, kan vi frit forbinde en knude med en anden, hvilket giver os muligheden for at oprette cyklusser. Den eneste undtagelse er, at en node ikke kan oprette forbindelse til sig selv.
Det er også værd at bemærke, at med denne repræsentation er der ingen rodknude. Dette er ikke et problem, da vi også gjorde forbindelserne mellem noder tovejs. Det betyder, at vi er i stand til at søge gennem grafen, der starter ved enhver node.
Lad os først og fremmest genbruge algoritmen ovenfra, tilpasset den nye struktur:
offentlig statisk Valgfri søgning (T-værdi, start af node) {Kø kø = ny ArrayDeque (); kø.tilføj (start); Node nuværendeNode; mens (! queue.isEmpty ()) {currentNode = queue.remove (); hvis (currentNode.getValue (). er lig med (værdi)) {return Optional.of (currentNode); } andet {queue.addAll (currentNode.getNeighbors ()); }} returner Optional.empty (); } Vi kan ikke køre algoritmen som denne, ellers vil en cyklus få den til at køre for evigt. Så vi skal tilføje instruktioner for at tage os af de allerede besøgte noder:
mens (! queue.isEmpty ()) {currentNode = queue.remove (); LOGGER.info ("Besøgt node med værdi: {}", currentNode.getValue ()); hvis (currentNode.getValue (). er lig med (værdi)) {return Optional.of (currentNode); } andet {alreadyVisited.add (currentNode); queue.addAll (currentNode.getNeighbors ()); kø.removeAll (allerede besøgt); }} returner Optional.empty ();Som vi kan se initialiserer vi først a Sæt der indeholder de besøgte noder.
Sæt alreadyVisited = ny HashSet (); Derefter, når sammenligningen af værdier mislykkes, tilføjer vi noden til de besøgte:
alreadyVisited.add (nuværendeNode);Langt om længe, efter at have tilføjet nodens naboer til køen fjerner vi de allerede besøgte noder fra den (som er en alternativ måde at kontrollere den aktuelle noders tilstedeværelse i det sæt):
queue.removeAll (alreadyVisited);Ved at gøre dette sørger vi for, at algoritmen ikke falder i en uendelig løkke.
Lad os se, hvordan det fungerer gennem et eksempel. Først og fremmest definerer vi en graf med en cyklus:
Og det samme i Java-kode:
Node start = ny node (10); Node firstNeighbor = ny Node (2); start.connect (firstNeighbor); Node firstNeighborNeighbor = ny Node (3); firstNeighbor.connect (firstNeighborNeighbor); firstNeighborNeighbor.connect (start); Node secondNeighbor = ny Node (4); start.connect (secondNeighbor);Lad os igen sige, at vi vil søge efter værdien 4. Da der ikke er nogen rodknude, kan vi begynde søgningen med den knude, vi ønsker, og vi vælger firstNeighborNeighbor:
BreadthFirstSearchAlgorithm.search (4, firstNeighborNeighbor);Igen tilføjer vi en log for at se, hvilke noder der er besøgt, og vi forventer, at de er 3, 2, 10 og 4, kun en gang hver i den rækkefølge:
[main] INFO cbabBreadthFirstSearchAlgorithm - Besøgt node med værdi: 3 [main] INFO cbabBreadthFirstSearchAlgorithm - Besøgt node med værdi: 2 [main] INFO cbabBreadthFirstSearchAlgorithm - Besøgt node med værdi: 10 [main] INFO cbabBreadth Vised node - værdi besøgte : 43.3. Kompleksitet
Nu hvor vi har dækket begge algoritmer i Java, lad os tale om deres tidskompleksitet. Vi bruger Big-O notationen til at udtrykke dem.
Lad os starte med træalgoritmen. Det føjer en knude til køen højst en gang, og derfor besøger den højst en gang også. Således, hvis n er antallet af noder i træet, vil algoritmens tidskompleksitet være På).
For grafalgoritmen er tingene nu lidt mere komplicerede. Vi går højst gennem hver node én gang, men for at gøre det bruger vi operationer, der har lineær kompleksitet som f.eks tilføjAlle () og Fjern alt().
Lad os overveje n antallet af noder og c antallet af forbindelser i grafen. Derefter kan vi i værste fald (da der ikke er fundet nogen node) bruge det tilføjAlle () og Fjern alt() metoder til at tilføje og fjerne noder op til antallet af forbindelser, hvilket giver os O (c) kompleksitet for disse operationer. Så forudsat at c> nvil kompleksiteten af den samlede algoritme være O (c). Ellers vil det være På). Dette bemærkes generelt O (n + c), som kan fortolkes som en kompleksitet afhængigt af det største antal imellem n og c.
Hvorfor havde vi ikke dette problem til træsøgningen? Fordi antallet af forbindelser i et træ er afgrænset af antallet af noder. Antallet af forbindelser i et træ af n noder er n - 1.
4. Konklusion
I denne artikel lærte vi om Breadth-First Search-algoritmen, og hvordan man implementerer den i Java.
Efter at have gennemgået en smule teori så vi Java-implementeringer af algoritmen og diskuterede dens kompleksitet.
Som sædvanlig er koden tilgængelig på GitHub.
