Breedte-eerste zoekalgoritme in Java

1. Overzicht

In deze tutorial gaan we leren over het Breadth-First Search-algoritme, waarmee we naar een knooppunt in een boom of een grafiek kunnen zoeken door door hun knooppunten eerst breedte-eerst dan diepte-eerst te reizen.

Eerst zullen we een stukje theorie doornemen over dit algoritme voor bomen en grafieken. Daarna duiken we in de implementaties van de algoritmen in Java. Ten slotte bespreken we hun tijdscomplexiteit.

2. Breedte-eerste zoekalgoritme

De basisbenadering van het Breadth-First Search (BFS) -algoritme is om naar een knooppunt in een boom- of grafiekstructuur te zoeken door buren vóór kinderen te verkennen.

Eerst zullen we zien hoe dit algoritme werkt voor bomen. Daarna zullen we het aanpassen aan grafieken, die de specifieke beperking hebben dat ze soms cycli bevatten. Ten slotte bespreken we de prestaties van dit algoritme.

2.1. Bomen

Het idee achter het BFS-algoritme voor bomen is om houd een rij knooppunten bij die de volgorde van doorgang garanderen. Aan het begin van het algoritme bevat de wachtrij alleen het hoofdknooppunt. We herhalen deze stappen zolang de wachtrij nog een of meer knooppunten bevat:

  • Pop het eerste knooppunt uit de wachtrij
  • Als dat knooppunt het knooppunt is waarnaar we op zoek zijn, is het zoeken voorbij
  • Voeg anders de onderliggende items van dit knooppunt toe aan het einde van de wachtrij en herhaal de stappen

De beëindiging van de uitvoering wordt verzekerd door de afwezigheid van cycli. In de volgende sectie zullen we zien hoe u cycli kunt beheren.

2.2. Grafieken

Bij grafieken moeten we denken aan mogelijke cycli in de structuur. Als we simpelweg het vorige algoritme toepassen op een grafiek met een cyclus, zal het voor altijd doorlopen. Daarom we moeten een verzameling van de bezochte knooppunten bijhouden en ervoor zorgen dat we ze niet twee keer bezoeken:

  • Pop het eerste knooppunt uit de wachtrij
  • Controleer of het knooppunt al is bezocht, sla het dan over
  • Als dat knooppunt het knooppunt is waarnaar we op zoek zijn, is het zoeken voorbij
  • Voeg het anders toe aan de bezochte knooppunten
  • Voeg de kinderen van dit knooppunt toe aan de wachtrij en herhaal deze stappen

3. Implementatie in Java

Nu de theorie is behandeld, gaan we de code in handen krijgen en deze algoritmen in Java implementeren!

3.1. Bomen

Eerst implementeren we het boom-algoritme. Laten we onze Boom class, die bestaat uit een waarde en kinderen vertegenwoordigd door een lijst met andere Booms:

openbare klasse Tree {privé T-waarde; privélijst kinderen; private Tree (T-waarde) {this.value = value; this.children = nieuwe ArrayList (); } openbare statische boom van (T-waarde) {retourneer nieuwe boom (waarde); } openbare Tree addChild (T-waarde) {Tree newChild = nieuwe Tree (waarde); children.add (newChild); retourneer newChild; }}

Om te voorkomen dat er cycli worden gemaakt, worden kinderen door de klas zelf gemaakt, op basis van een bepaalde waarde.

Laten we daarna een zoeken() methode:

public static Optioneel zoeken (T-waarde, Tree root) {// ...}

Zoals we eerder al zeiden, het BFS-algoritme gebruikt een wachtrij om de knooppunten te doorkruisen. Allereerst voegen we onze wortel knooppunt naar deze wachtrij:

Wachtrij wachtrij = nieuwe ArrayDeque (); queue.add (root);

Vervolgens moeten we een lus maken terwijl de wachtrij niet leeg is, en elke keer dat we een knooppunt uit de wachtrij halen:

while (! queue.isEmpty ()) {Tree currentNode = queue.remove (); }

Als dat knooppunt het knooppunt is waarnaar we zoeken, geven we het terug, anders voegen we de onderliggende knooppunten toe aan de wachtrij:

if (currentNode.getValue (). equals (waarde)) {return Optioneel.of (currentNode); } anders {queue.addAll (currentNode.getChildren ()); }

Ten slotte, als we alle knooppunten hebben bezocht zonder het knooppunt te vinden waarnaar we op zoek zijn, retourneren we een leeg resultaat:

return Optioneel.empty ();

Laten we ons nu een voorbeeld van een boomstructuur voorstellen:

Wat zich vertaalt in de Java-code:

Boomwortel = Tree.of (10); Tree rootFirstChild = root.addChild (2); Boom depthMostChild = rootFirstChild.addChild (3); Tree rootSecondChild = root.addChild (4);

Als we vervolgens naar de waarde 4 zoeken, verwachten we dat het algoritme knooppunten doorloopt met de waarden 10, 2 en 4, in die volgorde:

BreadthFirstSearchAlgorithm.search (4, root)

We kunnen dat verifiëren door de waarde van de bezochte knooppunten te loggen:

[main] INFO c.b.a.b.BreadthFirstSearchAlgorithm - Bezocht knooppunt met waarde: 10 [hoofd] INFO c.b.a.b.BreadthFirstSearchAlgorithm - Bezocht knooppunt met waarde: 2 [hoofd] INFO c.b.a.b.BreadthFirstSearchAlgorithm - Bezocht knooppunt met waarde: 4

3.2. Grafieken

Dat concludeert het geval van bomen. Laten we nu eens kijken hoe we met grafieken moeten omgaan. In tegenstelling tot bomen kunnen grafieken cycli bevatten. Dat betekent, zoals we in de vorige sectie hebben gezien, we moeten de knooppunten die we hebben bezocht onthouden om een ‚Äč‚Äčoneindige lus te vermijden. We zullen straks zien hoe we het algoritme kunnen bijwerken om dit probleem te overwegen, maar laten we eerst onze grafiekstructuur definiëren:

public class Node {private T-waarde; privé Set buren; public Node (T-waarde) {this.value = value; this.neighbours = nieuwe HashSet (); } public void connect (Node node) {if (this == node) werpt nieuwe IllegalArgumentException ("Kan knoop niet met zichzelf verbinden"); this.neighbours.add (knooppunt); node.neighbours.add (dit); }}

Nu kunnen we zien dat we, in tegenstelling tot bomen, vrijelijk een knoop met een andere kunnen verbinden, waardoor we de mogelijkheid hebben om cycli te creëren. De enige uitzondering is dat een knooppunt geen verbinding met zichzelf kan maken.

Het is ook vermeldenswaard dat er met deze weergave geen root-node is. Dit is geen probleem, aangezien we ook de verbindingen tussen knooppunten bidirectioneel hebben gemaakt. Dat betekent dat we door de grafiek kunnen zoeken, beginnend bij elk knooppunt.

Laten we allereerst het algoritme van boven hergebruiken, aangepast aan de nieuwe structuur:

public static Optioneel search (T-waarde, Node start) {Queue wachtrij = nieuwe ArrayDeque (); queue.add (start); Knooppunt currentNode; while (! queue.isEmpty ()) {currentNode = queue.remove (); if (currentNode.getValue (). equals (waarde)) {return Optioneel.of (currentNode); } anders {queue.addAll (currentNode.getNeighbours ()); }} return Optioneel.empty (); }

We kunnen het algoritme niet op deze manier uitvoeren, anders loopt het door elke cyclus voor altijd. We moeten dus instructies toevoegen om voor de reeds bezochte knooppunten te zorgen:

while (! queue.isEmpty ()) {currentNode = queue.remove (); LOGGER.info ("Bezochte knoop met waarde: {}", currentNode.getValue ()); if (currentNode.getValue (). equals (waarde)) {return Optioneel.of (currentNode); } else {alVisited.add (currentNode); queue.addAll (currentNode.getNeighbours ()); queue.removeAll (al bezocht); }} return Optioneel.empty ();

Zoals we kunnen zien, initialiseren we eerst een Set dat bevat de bezochte knooppunten.

Set alVisited = nieuwe HashSet ();

Dan, als de vergelijking van waarden mislukt, voegen we het knooppunt toe aan de bezochte:

alVisited.add (currentNode);

Tenslotte, na het toevoegen van de buren van het knooppunt aan de wachtrij, verwijderen we de reeds bezochte knooppunten eruit (wat een alternatieve manier is om de aanwezigheid van het huidige knooppunt in die set te controleren):

queue.removeAll (al bezocht);

Door dit te doen, zorgen we ervoor dat het algoritme niet in een oneindige lus terechtkomt.

Laten we aan de hand van een voorbeeld kijken hoe het werkt. Allereerst definiëren we een grafiek met een cyclus:

En hetzelfde in Java-code:

Knooppunt start = nieuw knooppunt (10); Knooppunt firstNe Neighbor = nieuw knooppunt (2); start.connect (eerste buur); Knooppunt firstNe NeighborNe Neighbor = nieuw knooppunt (3); firstNe Neighbor.connect (eerste buurman); firstNe NeighborNe Neighbor.connect (start); Knooppunt secondNe Neighbor = nieuw knooppunt (4); start.connect (secondNe Neighbor);

Laten we nogmaals zeggen dat we willen zoeken naar de waarde 4. Aangezien er geen root-knooppunt is, kunnen we de zoekopdracht beginnen met elk gewenst knooppunt en kiezen we eerste buurman:

BreadthFirstSearchAlgorithm.search (4, firstNe NeighborNe Neighbor);

Nogmaals, we zullen een logboek toevoegen om te zien welke knooppunten worden bezocht, en we verwachten dat ze 3, 2, 10 en 4 zijn, elk slechts één keer in die volgorde:

[main] INFO cbabBreadthFirstSearchAlgorithm - Bezochte node met waarde: 3 [main] INFO cbabBreadthFirstSearchAlgorithm - Bezochte node met waarde: 2 [main] INFO cbabBreadthFirstSearchAlgorithm - Bezochte node met waarde: 10 [main] INFO node met waarde: 10 [main] INFO node cbithabSearch : 4

3.3. Complexiteit

Nu we beide algoritmen in Java hebben behandeld, laten we het hebben over hun tijdcomplexiteit. We gebruiken de Big-O-notatie om ze uit te drukken.

Laten we beginnen met het boom-algoritme. Het voegt een knooppunt maximaal één keer toe aan de wachtrij en bezoekt het dus maximaal één keer. Dus als n is het aantal knooppunten in de boom, de tijdcomplexiteit van het algoritme zal zijn Aan).

Nu, voor het grafiekalgoritme, zijn de dingen een beetje gecompliceerder. We zullen elk knooppunt maximaal één keer doorlopen, maar hiervoor maken we gebruik van bewerkingen met lineaire complexiteit, zoals Voeg alles toe() en Verwijder alles().

Laat ons nadenken n het aantal knooppunten en c het aantal aansluitingen van de grafiek. In het ergste geval (omdat er geen knooppunt is gevonden), kunnen we Voeg alles toe() en Verwijder alles() methoden om knooppunten toe te voegen en te verwijderen tot het aantal verbindingen, waardoor we O (c) complexiteit voor deze operaties. Dus op voorwaarde dat c> n, zal de complexiteit van het algehele algoritme zijn O (c). Anders zal het zijn Aan). Dit wordt algemeen opgemerkt O (n + c), die kan worden geïnterpreteerd als een complexiteit, afhankelijk van het grootste aantal tussen n en c.

Waarom hadden we dit probleem niet bij het zoeken naar bomen? Omdat het aantal verbindingen in een boom wordt begrensd door het aantal knooppunten. Het aantal verbindingen in een boomstructuur van n knooppunten is n - 1.

4. Conclusie

In dit artikel hebben we geleerd over het Breadth-First Search-algoritme en hoe het in Java kan worden geïmplementeerd.

Nadat we wat theorie hadden doorgenomen, zagen we Java-implementaties van het algoritme en bespraken we de complexiteit ervan.

Zoals gewoonlijk is de code beschikbaar op GitHub.