Breadth First Search (BFS) Algoritme med EKSEMPEL
Sarah Chen
⚡ Smart oppsummering
Breddesøk (BFS) er en algoritme som går gjennom en graf nivå for nivå, og besøker alle naboer til en node før den går dypere. Den bruker en FIFO-kø og finner den korteste banen i uvektede grafer uten uendelige løkker.
Hva er BFS Algorithm (Bredth-First Search)?
Bredde-først-søk (BFS) er en algoritme som brukes til å lage grafer for data, søke i et tre eller krysse strukturer. Den fulle formen for BFS er bredde-først-søk.
Algoritmen besøker og merker effektivt alle nøkkelnodene i en graf på en nøyaktig breddevis måte. Denne algoritmen velger en enkelt node (start- eller kildepunkt) i en graf og besøker deretter alle nodene ved siden av den valgte noden. Husk at BFS får tilgang til disse nodene én etter én.
Når algoritmen besøker og markerer startnoden, beveger den seg mot de nærmeste ubesøkte nodene og analyserer dem. Når de er besøkt, er alle noder merket. Disse iterasjonene fortsetter til alle nodene i grafen har blitt besøkt og merket.
Hva er Graph-traversals?
En grafovergang er en ofte brukt metodikk for å lokalisere toppunktet i grafen. Det er en avansert søkealgoritme som kan analysere grafen med hastighet og presisjon sammen med markering av sekvensen til de besøkte toppunktene. Denne prosessen lar deg raskt besøke hver node i en graf uten å være låst i en uendelig sløyfe.
Arkitekturen til BFS-algoritmen
- I de ulike datanivåene kan du markere en hvilken som helst node som start- eller innledende node for å begynne å bevege deg. BFS-en vil besøke noden, markere den som besøkt og plassere den i køen.
- Nå vil BFS besøke de nærmeste og ubesøkte nodene og markere dem. Disse verdiene legges også til i køen. Køen fungerer på FIFO-modell.
- På lignende måte analyseres, merkes og legges de gjenværende nærmeste og ubesøkte nodene på grafen til køen. Disse elementene slettes fra køen etter hvert som de mottas, og skrives ut som resultat.
Hvorfor trenger vi BFS-algoritme?
Det finnes en rekke grunner til å bruke BFS-algoritmen for å søke i datasettet ditt. Noen av de viktigste aspektene som gjør denne algoritmen til ditt førstevalg er:
- BFS er nyttig for å analysere nodene i en graf og konstruere den korteste veien for å krysse gjennom disse.
- BFS kan gå gjennom en graf i det minste antall iterasjoner.
- Arkitekturen til BFS-algoritmen er enkel og robust.
- Resultatet av BFS-algoritmen holder et høyt nivå av nøyaktighet sammenlignet med andre algoritmer.
- BFS-iterasjoner er sømløse, og det er ingen mulighet for at denne algoritmen blir fanget opp i et problem med uendelig løkke.
Hvordan fungerer BFS-algoritmen?
Gjennomgang av grafer krever at algoritmen besøker, sjekker og/eller oppdaterer hver eneste ubesøkte node i en trelignende struktur. Grafgjennomganger er kategorisert etter rekkefølgen de besøker nodene på grafen.
BFS-algoritmen starter operasjonen fra den første eller startnoden i en graf og krysser den grundig. Så snart den har krysset den innledende noden, besøkes og markeres neste ikke-traverserte toppunkt i grafen.
Derfor kan man si at alle nodene ved siden av det nåværende toppunktet besøkes og krysses i den første iterasjonen. En enkel kømetodikk brukes til å implementere virkemåten til en BFS-algoritme, og den består av følgende trinn:
Trinn 1)
Hvert toppunkt eller node i grafen er kjent. Du kan for eksempel merke noden som V.
Trinn 2)
Hvis hjørnet V ikke er tilgjengelig, legg det til i BFS-køen.
Trinn 3)
Start BFS-søket, og merk hjørne V som besøkt etter at det er fullført.
Trinn 4)
BFS-køen er fortsatt ikke tom, fjern derfor toppunktet V på grafen fra køen.
Trinn 5)
Hent frem alle de gjenværende hjørnene på grafen som ligger inntil hjørnet V.
Trinn 6)
For hvert tilstøtende hjørne, la oss si V1, i tilfelle det ikke er besøkt ennå, legg deretter V1 til i BFS-køen.
Trinn 7)
BFS vil besøke V1, markere den som besøkt og slette den fra køen.
Eksempel BFS-algoritme
Trinn 1)
Du har en graf med sju tall fra 0 til 6.
Trinn 2)
0 eller null er merket som en rotnode.
Trinn 3)
0 besøkes, merkes og settes inn i kødatastrukturen.
Trinn 4)
De resterende 0-tilstøtende og ubesøkte nodene besøkes, merkes og settes inn i køen.
Trinn 5)
Gjennomgående iterasjoner gjentas til alle noder er besøkt.
Regler for BFS Algorithm
Her er viktige regler for bruk av BFS-algoritmen:
- En kø (FIFO – først inn, først ut) data struktur brukes av BFS.
- Du markerer en hvilken som helst node i grafen som roten og begynner å krysse dataene fra den.
- BFS krysser alle nodene i grafen og fortsetter å slippeping dem som fullførte.
- BFS besøker en tilstøtende ubesøkt node, merker den som ferdig og setter den inn i en kø.
- Den fjerner det forrige hjørnet fra køen dersom ingen tilstøtende hjørne blir funnet.
- BFS-algoritmen itererer til alle hjørnene i grafen er krysset og merket som fullført.
- Det er ingen løkker forårsaket av BFS under kryssing av data fra noen node.
Anvendelser av BFS Algorithm
La oss ta en titt på noen av de virkelige applikasjonene der en BFS-algoritmeimplementering kan være svært effektiv.
- Uvektede grafer: BFS-algoritmen kan enkelt lage den korteste banen og et minimumspenntre for å besøke alle hjørnene i grafen på kortest mulig tid med høy nøyaktighet.
- P2P-nettverk: BFS kan implementeres for å finne alle nærmeste eller nærliggende noder i et peer-to-peer-nettverk. Dette vil finne de nødvendige dataene raskere.
- Webcrawlere: Søkemotorer eller webcrawlere kan enkelt bygge flere nivåer av indekser ved å bruke BFS. BFS-implementering starter fra kilden, som er nettsiden, og deretter besøker den alle koblingene fra den kilden.
- Navigasjonssystemer: BFS kan hjelpe med å finne alle nærliggende steder fra hoved- eller kildestedet.
- Nettverkskringkasting: En kringkastet pakke blir guidet av BFS-algoritmen for å finne og nå alle nodene den har adressen til.
