Når det gjelder læring, er det generelt to tilnærminger man kan ta: du kan enten gå bredt, og prøv å dekke så mye av spekteret av et felt som mulig, ellers kan du gå dypt, og prøve å bli veldig, veldig spesifikk med emnet du lærer. De fleste gode elever vet at til en viss grad alt du lærer i livet – fra algoritmer til grunnleggende livsferdigheter – involverer en kombinasjon av disse to tilnærmingene.

Det samme gjelder informatikk, problemløsning, og datastrukturer. I forrige uke dykket vi dypt inn i første dybdesøk og lærte hva det vil si å faktisk krysse gjennom et binært søketre. Nå som vi har gått dypt, er det fornuftig for oss å gå bredt og forstå den andre vanlige treovergangsstrategien.

Med andre ord, det er øyeblikket dere alle har ventet på: det er på tide å bryte ned det grunnleggende om bredde-første-søk!

En av de beste måtene å forstå hva bredde-første-søk (BFS) er, er å forstå hva det ikke er. Det vil si at hvis vi sammenligner BFS med DFS, vil det være mye lettere for oss å holde dem rett i hodet. Så la oss friske opp minnet om dybde-første-søk før vi går videre.

Vi vet at dybde-første-søk er prosessen med å krysse ned gjennom en gren av et tre til vi kommer til et blad, og deretter jobbe oss tilbake til «stammen» på treet. Med andre ord betyr implementering av en DFS å krysse nedover gjennom undertrærne til et binært søketre.

Ok, så hvordan gjør bredde-først Hvis vi tenker på det, er det eneste virkelige alternativet til å reise ned en gren av et tre og deretter en annen å reise nedover treet seksjon for seksjon – eller nivå for nivå. Og det er akkurat hva BFS er !

Bredde-første-søk innebærer søk gjennom et tre om gangen.

Vi krysse gjennom ett helt nivå av barnenoder først, før du går videre til å krysse gjennom barnebarnodene. Og vi krysser gjennom et helt nivå av barnebarn-noder før vi fortsetter å krysse gjennom oldebarn-noder.

OK, det virker ganske klart. Hva mer skiller de to forskjellige typene av algoritmer for traversering av tre? Vi har allerede dekket forskjellene i prosedyrene for disse to algoritmene. La oss tenke på det andre viktige aspektet vi ikke har snakket om ennå: implementering.

La oss først begynne med det vi vet. Hvordan gikk vi i gang med å implementere dybde-første søk i forrige uke? Du husker kanskje at vi lærte tre forskjellige metoder – bestilling, etterbestilling og forhåndsbestilling – for å søke gjennom et tre ved hjelp av DFS. Likevel var det noe superkult over hvor like disse tre implementeringene; de kunne hver ansettes ved hjelp av rekursjon. Vi vet også at siden DFS kan skrives som en rekursiv funksjon, kan de føre til at samtalestakken blir like stor som den lengste banen i treet.

Det var imidlertid en ting jeg forlot ut i forrige uke som det virker bra å ta opp nå (og kanskje det til og med litt opplagt!): samtalestakken implementerer faktisk en stabeldatastruktur. Husker du de? Vi lærte om stabler for en stund siden, men her er de igjen og dukker opp overalt!

Det virkelig interessante med å implementere dybdeforsøk med en stabel er at når vi går gjennom undertrærne til en binært søketre, blir hver av nodene vi «sjekker» eller «besøker» lagt til i bunken. Når vi når en bladnode – en node som ikke har barn – begynner vi å kutte av nodene fra toppen av stabelen. Vi havner ved rotnoden igjen, og kan deretter fortsette å krysse nedover i neste undertre.

I eksempel DFS-treet ovenfor, vil du legge merke til at nodene 2, 3 og 4 alle blir lagt til toppen av stabelen. Når vi kommer til «slutten» av det subtreet – det vil si når vi når bladknutepunktene 3 og 4 – begynner vi å skyve av disse nodene fra bunken vår med «noder å besøke».Du kan se hva som til slutt vil skje med riktig undertre: nodene du skal besøke, blir presset på samtalestakken, vi besøker dem og vil systematisk skyve dem ut av stabelen. har besøkt både venstre og høyre undertrær, vi kommer tilbake til rotnoden uten noe å sjekke, og samtalestakken vår vil være tom.

Så vi burde kunne bruke en stable strukturen og gjøre noe lignende med vår BFS-implementering … ikke sant? Vel, jeg vet ikke om det vil fungere, men jeg tror det vil være nyttig å i det minste starte med å tegne algoritmen vi vil implementere, og se hvor langt vi kan komme med den.

La oss prøve:

Ok, så vi har en graf til venstre som vi implementerte DFS i forrige uke. Hvordan kan vi bruke en BFS-algoritme på den i stedet?

Vel, for å starte, vet vi at vi først vil sjekke rotnoden. Det er den eneste noden vi har tilgang til i utgangspunktet, og så vil vi «peke» på noden f.

Greit, nå må vi sjekke barna til denne rotnoden.

Vi vil sjekke det ene barnet etter det andre, så la oss gå til det venstre barnet først – node d er noden vi «peker» mot nå (og den eneste noden vi har tilgang til).

Deretter vil vi gå til høyre barneknute.

Uh oh. Vent, rotnoden er ikke engang tilgjengelig for oss lenger! Og vi kan ikke bevege oss i omvendt retning, fordi binære trær ikke har omvendte lenker! Hvordan skal vi komme til riktig barneknute? Og … å nei, venstre barneknute d og høyre barneknut k er ikke koblet i det hele tatt. Så det betyr at det er umulig for oss å hoppe fra et barn til et annet fordi vi ikke har tilgang til noe annet enn barn til node.

Å kjære. Vi kom ikke veldig langt, gjorde vi? Vi må finne ut en annen metode for å løse dette problemet. Vi må finne ut av en måte å implementere en trepassasje på som lar oss gå i treet i jevn rekkefølge. Det viktigste vi må huske på er dette:

Vi trenger å holde en referanse til alle barnenoder i hver node vi besøker. Ellers vil vi aldri kunne gå tilbake til dem senere og besøke dem!

Jo mer jeg tenker på det, jo mer har jeg lyst til det er som om vi vil ha en liste over alle nodene vi fortsatt trenger å sjekke, ikke sant? Og i det øyeblikket jeg ønsker å holde en liste over noe, hopper tankene mine umiddelbart til en datastruktur spesielt: en kø, selvfølgelig!

La oss se om køer kan hjelpe oss med vår BFS-implementering. / p>

Køer til unnsetning!

Som det viser seg, er en stor forskjell i dybde-første søk og bredde-første søk datastrukturen som brukes til å implementere begge disse veldig forskjellige algoritmene.

Mens DFS bruker en stabeldatastruktur, lener BFS seg på kødatastrukturen. Det fine med å bruke køer er at det løser selve problemet vi oppdaget tidligere: det lar oss beholde en referanse til noder som vi vil komme tilbake til, selv om vi ikke har sjekket / besøkt dem ennå.

Vi legger til noder som vi har oppdaget – men ennå ikke har besøkt – i køen vår, og kommer tilbake til dem senere.

Et vanlig begrep for noder som vi legger til i køen vår er oppdagede noder; en oppdaget node er en som vi legger til i køen, hvis beliggenhet vi vet, men vi har ennå ikke besøkt. Dette er faktisk akkurat det som gjør en kø til den perfekte strukturen for å løse BFS-problemet.

I grafen til venstre starter vi med å legge til rotnoden i køen vår, siden det er den eneste noden vi noen gang har ha tilgang til (i det minste i utgangspunktet) i et tre. Dette betyr at rotnoden er den eneste oppdagede noden som begynner.

Når vi har minst en node påkjørt, kan vi starte prosessen med å besøke noder, og legge til referanser til deres barn noder i køen vår.

Ok, så alt dette høres kanskje litt forvirrende ut. Og det er greit! Jeg tror det vil være mye lettere å forstå hvis vi deler det opp i enklere trinn.

For hver node i køen vår – alltid å starte med rotnoden – vil vi gjøre tre ting:

1. Besøk noden, som vanligvis bare betyr å skrive ut verdien.
2. Legg til nodenes venstre barn i køen vår.
3. Legg til nodenes høyre barn til køen vår.

Når vi har gjort disse tre tingene, kan vi fjerne noden fra køen vår, fordi vi ikke trenger den lenger!Vi må i grunn fortsette å gjøre dette gjentatte ganger til vi kommer til det punktet hvor køen vår er tom.

Ok, la oss se på dette i aksjon!

I grafen nedenfor begynner vi av med rotnoden, node f, som den eneste oppdagede noden. Husker vi de tre trinnene våre? La oss gjøre dem nå:

1. Vi besøker node f og skriver ut verdien.
2. Vi legger inn en referanse til venstre barn, node d.
3. Vi tar en referanse til det rette barnet sitt, node k.

Og så fjerner vi node f fra køen!

Den neste noden foran i køen er node d. Igjen, de samme tre trinnene her: skriv ut verdien, legg til venstre barn, legg til høyre barn, og fjern det deretter fra køen.

Køen vår har nå referanser til nodene k, b og e . Hvis vi fortsetter å gjenta denne prosessen systematisk, vil vi merke at vi faktisk krysser grafen og skriver ut nodene i nivå. Hurra! Det er akkurat det vi ønsket å gjøre i utgangspunktet.

Nøkkelen til at dette fungerer så bra er selve naturen til køstrukturen. Køer følger først-inn-først-ut-prinsippet (FIFO), noe som betyr at det som først ble innhentet, er det første elementet som blir lest og fjernet fra køen.

Til slutt, mens vi er på temaet køer, er det verdt å nevne at romtidskompleksiteten til en BFS-algoritme også er relatert til køen vi bruker for å implementere den – hvem visste at køene ville komme tilbake for å være så nyttig, ikke sant?

Tidskompleksiteten til en BFS-algoritme avhenger direkte av hvor lang tid det tar å besøke en node. Siden tiden det tar å lese en nodes verdi og innhente barna, ikke endres basert på noden, kan vi si at det å besøke en node tar konstant tid, eller O (1) tid. Siden vi bare besøker hver node i et BFS-treet gjennom en gang, avhenger egentlig tiden av å lese hver node bare av hvor mange noder det er i treet! Hvis treet vårt har 15 noder, vil det ta oss O (15); men hvis treet vårt har 1500 noder, vil det ta oss O (1500). Dermed tar tidskompleksiteten til en bredde-første-søkealgoritme lineær tid, eller O (n), hvor n er antall noder i treet.

Romkompleksitet er lik dette, har mer å gjøre med hvor mye køen vår vokser og krymper når vi legger til nodene vi trenger å sjekke til den. I verste fall kan vi potensielt omslutte alle noder i et tre hvis de alle er barn av hverandre, noe som betyr at vi muligens kan bruke så mye minne som det er noder i treet. Hvis størrelsen på køen kan vokse til antall noder i treet, er romkompleksiteten for en BFS-algoritme også lineær tid, eller O (n), hvor n er antall noder i treet.

Dette er vel og bra, men vet du hva jeg virkelig vil gjøre akkurat nå? Jeg vil faktisk skrive en av disse algoritmene! La oss omsider praktisere all denne teorien.

Koding av vår første bredeste-første søkealgoritme

Vi har klart det! Vi skal endelig kode vår aller første BFS-algoritme. Vi gjorde litt av dette i forrige uke med DFS-algoritmer, så la oss prøve å skrive en bred første søk-implementering av dette også.

Du husker kanskje at vi skrev dette i vanilje JavaScript forrige uke, så vi holder oss til det igjen for konsistens skyld. I tilfelle du trenger en rask oppfriskning, bestemte vi oss for å holde det enkelt, og skrive nodeobjektene våre som Plain Old JavaScript Objects (POJO’s), slik:

node1 = {
data: 1,
left: referenceToLeftNode,
right: referenceToRightNode
};

Ok, kult. Ett trinn gjort.

Men nå som vi vet om køer og er sikre på at vi må bruke en for å implementere denne algoritmen … bør vi nok finne ut hvordan vi gjør det i JavaScript, ikke sant? Vel, som det viser seg, er det veldig enkelt å lage et kølignende objekt i JS!

Vi kan bruke en matrise, noe som gjør kunsten ganske pent:

Hvis vi ville gjøre dette litt mer avansert, kunne vi sannsynligvis også lage et Queue objekt, som kan ha en praktisk funksjon som top eller isEmpty; men foreløpig vil vi stole på veldig enkel funksjonalitet.

Ok, la oss skrive denne valpen! Vi oppretter en levelOrderSearch -funksjon som tar inn et rootNode -objekt.

Kjempebra! Dette er faktisk … ganske enkelt. Eller i det minste mye enklere enn jeg forventet å være. Alt vi gjør her er å bruke en while sløyfe for å fortsette å gjøre de tre trinnene for å sjekke en node, legge til venstre barn og legge til høyre barn.Vi fortsetter å gjenta gjennom queue matrisen til alt er fjernet fra den, og lengden er 0.

Fantastisk. Vår algoritmeekspertise har steget til været på bare en dag! Ikke bare vet vi hvordan vi skal skrive rekursive algoritmer for tregjennomgang, men nå vet vi også hvordan vi skal skrive iterative. Hvem visste at algoritmiske søk kan være så bemyndigende!

Ressurser

Det er fortsatt mye å lære om bredeste første søk, og når det kan være nyttig. Heldigvis er det mange ressurser som dekker informasjon som jeg ikke kunne passe inn i dette innlegget. Ta en titt på noen av de virkelig gode nedenfor.

1. DFS og BFS algoritmer ved hjelp av stabler og køer, professor Lawrence L. Larmore
2. Algoritmen Breadth-First Search, Khan Akademi
3. Datastruktur – Breadth First Traversal, TutorialsPoint
4. Binary tree: Level Order Traversal, mycodeschool
5. Breadth-First Traversal of a Tree, Computer Science Department of Boston University