Breadth First Search (BFS) Algoritme med EKSEMPEL

Hvad er BFS Algorithm (Bredth-First Search)?

Breadth-first search (BFS) er en algoritme, der bruges til at tegne data eller søge i træer eller krydse strukturer. Den fulde form for BFS er Breadth-first-søgningen.

Algoritmen besøger og markerer effektivt alle nøgleknuder i en graf på en nøjagtig breddevis måde. Denne algoritme vælger en enkelt node (initial- eller kildepunkt) i en graf og besøger derefter alle noder, der støder op til den valgte node. Husk, at BFS får adgang til disse noder én efter én.

Når algoritmen besøger og markerer startknudepunktet, bevæger den sig mod de nærmeste ubesøgte knudepunkter og analyserer dem. Når de er besøgt, er alle noder markeret. Disse iterationer fortsætter, indtil alle knudepunkterne i grafen er blevet besøgt og markeret.

Hvad er Graph-traversals?

En grafgennemgang er en almindeligt anvendt metode til at lokalisere toppunktet i grafen. Det er en avanceret søgealgoritme, der kan analysere grafen med hastighed og præcision sammen med markering af rækkefølgen af ​​de besøgte hjørner. Denne proces giver dig mulighed for hurtigt at besøge hver knude i en graf uden at være låst i en uendelig løkke.

Arkitekturen af ​​BFS algoritme

1. På de forskellige niveauer af dataene kan du markere en hvilken som helst node som start- eller startknude for at begynde at krydse. BFS vil besøge noden og markere den som besøgt og placere den i køen.
2. Nu vil BFS besøge de nærmeste og ikke-besøgte noder og markere dem. Disse værdier tilføjes også til køen. Køen arbejder på FIFO model.
3. På lignende måde analyseres de resterende nærmeste og ikke-besøgte knudepunkter på grafen markeret og tilføjes til køen. Disse elementer slettes fra køen som modtagelse og udskrives som resultat.

Hvorfor har vi brug for BFS-algoritme?

Der er mange grunde til at bruge BFS-algoritmen til at bruge som søgning efter dit datasæt. Nogle af de mest vitale aspekter, der gør denne algoritme til dit første valg, er:

• BFS er nyttig til at analysere knudepunkterne i en graf og konstruere den korteste vej til at krydse gennem disse.
• BFS kan krydse en graf i det mindste antal iterationer.
• Arkitekturen af ​​BFS-algoritmen er enkel og robust.
• Resultatet af BFS-algoritmen har et højt niveau af nøjagtighed i sammenligning med andre algoritmer.
• BFS-iterationer er problemfrie, og der er ingen mulighed for, at denne algoritme bliver fanget af et problem med uendelig sløjfe.

Hvordan virker BFS-algoritmen?

Grafgennemgang kræver, at algoritmen besøger, tjekker og/eller opdaterer hver eneste ubesøgte node i en trælignende struktur. Grafgennemgange er kategoriseret efter den rækkefølge, de besøger knudepunkterne på grafen i.

BFS-algoritmen starter operationen fra den første eller startnode i en graf og gennemgår den grundigt. Når først den har krydset den indledende node, besøges og markeres det næste ikke-gennemløbede toppunkt i grafen.

Derfor kan du sige, at alle knudepunkter, der støder op til det nuværende toppunkt, besøges og krydses i den første iteration. En simpel kømetodologi bruges til at implementere en BFS-algoritme, og den består af følgende trin:

Trin 1)

Hvert knudepunkt eller knudepunkt i grafen er kendt. For eksempel kan du markere noden som V.

Trin 2)

Hvis der ikke er adgang til toppunktet V, skal du tilføje toppunktet V til BFS-køen

Trin 3)

Start BFS-søgningen, og efter afslutning markerer du toppunkt V som besøgt.

Trin 4)

BFS-køen er stadig ikke tom, og fjern derfor toppunktet V på grafen fra køen.

Trin 5)

Hent alle de resterende hjørner på grafen, der støder op til toppunktet V

Trin 6)

Lad os sige V1 for hvert tilstødende toppunkt, hvis det ikke er besøgt endnu, så føj V1 til BFS-køen

Trin 7)

BFS vil besøge V1 og markere den som besøgt og slette den fra køen.

Eksempel BFS-algoritme

Trin 1)

Du har en graf med syv tal fra 0 til 6.

Trin 2)

0 eller nul er blevet markeret som en rodnode.

Trin 3)

0 besøges, markeres og indsættes i køens datastruktur.

Trin 4)

Resterende 0 tilstødende og ubesøgte noder besøges, markeres og indsættes i køen.

Trin 5)

Gennemgående iterationer gentages, indtil alle noder er besøgt.

Regler for BFS Algorithm

Her er vigtige regler for brug af BFS-algoritme:

• En kø (FIFO-First in First Out) datastruktur bruges af BFS.
• Du markerer en hvilken som helst node i grafen som rod og begynder at krydse dataene fra den.
• BFS krydser alle knudepunkterne i grafen og bliver ved med at slippe dem, når de er afsluttet.
• BFS besøger en tilstødende ubesøgt node, markerer den som udført og indsætter den i en kø.
• Fjerner det forrige toppunkt fra køen, hvis der ikke findes nogen tilstødende toppunkt.
• BFS-algoritmen itererer, indtil alle toppunkterne i grafen er gennemført og markeret som afsluttet.
• Der er ingen sløjfer forårsaget af BFS under passage af data fra nogen knude.

Anvendelser af BFS Algorithm

Lad os tage et kig på nogle af de virkelige applikationer, hvor en BFS-algoritmeimplementering kan være yderst effektiv.

• Uvægtede grafer: BFS-algoritmen kan nemt skabe den korteste vej og et minimum spændingstræ for at besøge alle hjørnerne af grafen på kortest mulig tid med høj nøjagtighed.
• P2P-netværk: BFS kan implementeres til at lokalisere alle de nærmeste eller tilstødende noder i et peer-to-peer-netværk. Dette vil finde de nødvendige data hurtigere.
• Webcrawlere: Søgemaskiner eller webcrawlere kan nemt bygge flere niveauer af indekser ved at bruge BFS. BFS-implementering starter fra kilden, som er websiden, og derefter besøger den alle links fra den kilde.
• Navigationssystemer: BFS kan hjælpe med at finde alle de nærliggende steder fra hoved- eller kildeplaceringen.
• Netværksudsendelse: En udsendt pakke styres af BFS-algoritmen til at finde og nå alle de noder, den har adressen til.

Resumé

• En grafgennemgang er en unik proces, der kræver, at algoritmen besøger, tjekker og/eller opdaterer hver eneste ikke-besøgte node i en trælignende struktur. BFS-algoritmen fungerer efter et lignende princip.
• Algoritmen er nyttig til at analysere knudepunkterne i en graf og konstruere den korteste vej gennem disse.
• Algoritmen krydser grafen i det mindste antal iterationer og den kortest mulige tid.
• BFS vælger en enkelt knude (initial- eller kildepunkt) i en graf og besøger derefter alle knudepunkter, der støder op til den valgte knude. BFS får adgang til disse noder én efter én.
• De besøgte og markerede data sættes i kø af BFS. En kø fungerer efter først ind først ud basis. Derfor slettes det element, der er placeret i grafen først, først og udskrives som et resultat.
• BFS-algoritmen kan aldrig blive fanget i en uendelig løkke.
• På grund af høj præcision og robust implementering bruges BFS i flere virkelige løsninger som P2P-netværk, webcrawlere og netværksudsendelser.