Bredde-første søkealgoritme i Java
1. Oversikt
I denne opplæringen skal vi lære om Breadth-First Search-algoritmen, som lar oss søke etter en node i et tre eller en graf ved å reise gjennom nodenes bredde først i stedet for dybde først.
Først vil vi gå gjennom litt teori om denne algoritmen for trær og grafer. Etter det vil vi dykke ned i implementeringene av algoritmene i Java. Til slutt vil vi dekke deres tidskompleksitet.
2. Bredde-første søkealgoritme
Den grunnleggende tilnærmingen til BFS-algoritmen (Breadth-First Search) er å søke etter en node i et tre eller en grafstruktur ved å utforske naboer før barn.
Først får vi se hvordan denne algoritmen fungerer for trær. Etter det vil vi tilpasse det til grafer, som har den spesifikke begrensningen å noen ganger inneholde sykluser. Til slutt vil vi diskutere ytelsen til denne algoritmen.
2.1. Trær
Ideen bak BFS-algoritmen for trær er å opprettholde en kø med noder som vil sikre rekkefølgen av traversering. I begynnelsen av algoritmen inneholder køen bare rotnoden. Vi gjentar disse trinnene så lenge køen fremdeles inneholder en eller flere noder:
- Popp den første noden fra køen
- Hvis den noden er den vi søker etter, er søket over
- Ellers legger du til denne nodens barn i slutten av køen og gjentar trinnene
Avslutning av utførelsen er sikret ved fravær av sykluser. Vi får se hvordan du administrerer sykluser i neste avsnitt.
2.2. Grafer
Når det gjelder grafer, må vi tenke på mulige sykluser i strukturen. Hvis vi bare bruker den forrige algoritmen på en graf med en syklus, vil den løkke for alltid. Derfor, vi må beholde en samling av de besøkte nodene og sørge for at vi ikke besøker dem to ganger:
- Popp den første noden fra køen
- Sjekk om noden allerede er besøkt, i så fall hopper du over den
- Hvis den noden er den vi søker etter, er søket over
- Ellers kan du legge den til de besøkte nodene
- Legg til denne nodens barn i køen og gjenta disse trinnene
3. Implementering i Java
Nå som teorien er dekket, la oss få koden vår og implementere disse algoritmene i Java!
3.1. Trær
Først implementerer vi trealgoritmen. La oss designe vår Tre klasse, som består av en verdi og barn representert av en liste over andre Tres:
offentlig klasse Tre {privat T-verdi; privat liste barn; private Tree (T-verdi) {this.value = verdi; this.children = new ArrayList (); } offentlig statisk tre av (T-verdi) {returner nytt tre (verdi); } public Tree addChild (T-verdi) {Tree newChild = nytt tre (verdi); childs.add (newChild); returner newChild; }} For å unngå å lage sykluser, blir barn skapt av klassen selv, basert på en gitt verdi.
Etter det, la oss gi en Søk() metode:
offentlig statisk Valgfritt søk (T-verdi, trerot) {// ...} Som vi nevnte tidligere, BFS-algoritmen bruker en kø for å krysse nodene. Først av alt legger vi til vår rot node til denne køen:
Kø kø = ny ArrayDeque (); kø.tillegge (rot); Så må vi løkke mens køen ikke er tom, og hver gang vi spretter ut en node fra køen:
while (! queue.isEmpty ()) {Tree currentNode = queue.remove (); }Hvis den noden er den vi søker etter, returnerer vi den, ellers legger vi barna til køen:
hvis (currentNode.getValue (). er lik (verdi)) {return Optional.of (currentNode); } annet {queue.addAll (currentNode.getChildren ()); }Til slutt, hvis vi besøkte alle nodene uten å finne den vi lette etter, returnerer vi et tomt resultat:
retur Optional.empty ();La oss nå forestille oss et eksempel på en trestruktur:
Som oversettes til Java-koden:
Tree root = Tree.of (10); Tree rootFirstChild = root.addChild (2); Tree depthMostChild = rootFirstChild.addChild (3); Tree rootSecondChild = root.addChild (4);Så hvis vi søker etter verdien 4, forventer vi at algoritmen skal krysse noder med verdiene 10, 2 og 4, i den rekkefølgen:
BreadthFirstSearchAlgorithm.search (4, root)Vi kan bekrefte at ved å logge verdien av de besøkte nodene:
[main] INFO c.b.a.b.BreadthFirstSearchAlgorithm - Besøkt node med verdi: 10 [main] INFO c.b.a.b.BreadthFirstSearchAlgorithm - Besøkt node med verdi: 2 [main] INFO c.b.a.b.BreadthFirstSearchAlgorithm - Besøkt node med verdi: 43.2. Grafer
Det avslutter tilfellet med trær. La oss nå se hvordan vi skal håndtere grafer. I motsetning til trær, kan grafer inneholde sykluser. Det betyr, som vi har sett i forrige avsnitt, vi må huske nodene vi besøkte for å unngå en uendelig løkke. Vi får se et øyeblikk hvordan vi kan oppdatere algoritmen for å vurdere dette problemet, men la oss først definere grafstrukturen vår:
offentlig klasse Node {privat T-verdi; privat sett naboer; offentlig node (T-verdi) {this.value = verdi; this.neighbors = nye HashSet (); } public void connect (Node node) {if (this == node) throw new IllegalArgumentException ("Can't connect node to itself"); this.neighbors.add (node); node.neighbors.add (dette); }} Nå kan vi se at, i motsetning til trær, kan vi fritt koble en node med en annen, noe som gir oss muligheten til å lage sykluser. Det eneste unntaket er at en node ikke kan koble seg til seg selv.
Det er også verdt å merke seg at det med denne representasjonen ikke er noen rotnode. Dette er ikke et problem, ettersom vi også gjorde forbindelsene mellom noder toveis. Det betyr at vi kan søke gjennom grafen fra hvilken som helst node.
La oss først bruke algoritmen ovenfra, tilpasset den nye strukturen:
offentlig statisk Valgfritt søk (T-verdi, Start-node) {Kø kø = ny ArrayDeque (); kø.tillegg (start); Node currentNode; mens (! queue.isEmpty ()) {currentNode = queue.remove (); hvis (currentNode.getValue (). er lik (verdi)) {return Optional.of (currentNode); } annet {queue.addAll (currentNode.getNeighbors ()); }} returner Optional.empty (); } Vi kan ikke kjøre algoritmen slik, eller noen syklus vil få den til å kjøre for alltid. Så vi må legge til instruksjoner for å ta vare på de allerede besøkte nodene:
mens (! queue.isEmpty ()) {currentNode = queue.remove (); LOGGER.info ("Besøkt node med verdi: {}", currentNode.getValue ()); hvis (currentNode.getValue (). er lik (verdi)) {return Optional.of (currentNode); } annet {alreadyVisited.add (currentNode); queue.addAll (currentNode.getNeighbors ()); queue.removeAll (alreadyVisited); }} returner Optional.empty ();Som vi ser, initialiserer vi først a Sett som inneholder de besøkte nodene.
Sett alreadyVisited = nye HashSet (); Deretter, når sammenligningen av verdier mislykkes, legger vi noden til de besøkte:
alreadyVisited.add (currentNode);Endelig, etter å ha lagt nodenes naboer til køen, fjerner vi de allerede besøkte nodene fra den (som er en alternativ måte å sjekke den nåværende nodens tilstedeværelse i det settet):
queue.removeAll (alreadyVisited);Ved å gjøre dette sørger vi for at algoritmen ikke faller i en uendelig løkke.
La oss se hvordan det fungerer gjennom et eksempel. Først og fremst definerer vi en graf med en syklus:
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);La oss igjen si at vi vil søke etter verdien 4. Siden det ikke er noen rotnode, kan vi begynne søket med hvilken node vi ønsker, og vi velger firstNeighborNeighbor:
BreadthFirstSearchAlgorithm.search (4, firstNeighborNeighbor);Igjen legger vi til en logg for å se hvilke noder som besøkes, og vi forventer at de skal være 3, 2, 10 og 4, bare en gang hver i den rekkefølgen:
[main] INFO cbabBreadthFirstSearchAlgorithm - Besøkt node med verdi: 3 [main] INFO cbabBreadthFirstSearchAlgorithm - Besøkt node med verdi: 2 [main] INFO cbabBreadthFirstSearchAlgorithm - Besøkt node med verdi: 10 [main] INFO cbabBreadth Visittnode : 43.3. Kompleksitet
Nå som vi har dekket begge algoritmene i Java, la oss snakke om deres tidskompleksitet. Vi bruker Big-O-notasjonen for å uttrykke dem.
La oss starte med trealgoritmen. Det legger til en node i køen på det meste en gang, og besøker den også på det meste en gang også. Dermed, hvis n er antall noder i treet, vil algoritmens tidskompleksitet være På).
Nå, for grafalgoritmen, er ting litt mer kompliserte. Vi vil gå gjennom hver node på det meste en gang, men for å gjøre det bruker vi operasjoner som har lineær kompleksitet som f.eks Legg til alle() og Fjern alle().
La oss vurdere n antall noder og c antall tilkoblinger i grafen. Så, i verste fall (det er ikke funnet en node), kan vi bruke det Legg til alle() og Fjern alle() metoder for å legge til og fjerne noder opp til antall tilkoblinger, noe som gir oss O (c) kompleksitet for disse operasjonene. Så forutsatt at c> nvil kompleksiteten til den generelle algoritmen være O (c). Ellers blir det det På). Dette bemerkes generelt O (n + c), som kan tolkes som en kompleksitet avhengig av det største antallet mellom n og c.
Hvorfor hadde vi ikke dette problemet for tresøket? Fordi antall tilkoblinger i et tre er avgrenset av antall noder. Antall tilkoblinger i et tre av n noder er n - 1.
4. Konklusjon
I denne artikkelen lærte vi om Breadth-First Search-algoritmen og hvordan du implementerer den i Java.
Etter å ha gått gjennom litt teori, så vi Java-implementeringer av algoritmen og diskuterte dens kompleksitet.
Som vanlig er koden tilgjengelig på GitHub.
