Breadth First Search (BFS)-algoritme met VOORBEELD

Wat is BFS-algoritme (Breadth-First Search)?

Breadth-first search (BFS) is een algoritme dat wordt gebruikt om gegevens of searchidoor bomen heen te gaan of structuren te doorkruisen. De volledige vorm van BFS is de breedte-eerst-zoekopdracht.

Het algoritme bezoekt en markeert efficiënt alle belangrijke knooppunten in een grafiek in een nauwkeurige breedtewise mode. Dit algoritme selecteert een enkel knooppunt (begin- of bronpunt) in een grafiek en bezoekt vervolgens alle knooppunten die grenzen aan het geselecteerde knooppunt. Onthoud dat BFS deze knooppunten één voor één benadert.

Zodra het algoritme het startknooppunt bezoekt en markeert, beweegt het zich naar het nieuwe knooppuntarest onbezochte knooppunten en analyseert deze. Eenmaal bezocht, worden alle knooppunten gemarkeerd. Deze iteraties gaan door totdat alle knooppunten van de grafiek met succes zijn bezocht en gemarkeerd.

Wat zijn grafiektraversals?

Een grafiektraversal is een veelgebruikte methodologie voor het lokaliseren van de hoekpuntpositie in de grafiek. Het is een geavanceerd zoekalgoritme dat de grafiek snel en nauwkeurig kan analyseren en de volgorde van de bezochte hoekpunten kan markeren. Met dit proces kunt u snel elk knooppunt in een grafiek bezoeken zonder vast te zitten in een oneindige lus.

Het archistructuur van het BFS-algoritme

Architectuur van het BFS-algoritme

  1. Op de verschillende gegevensniveaus kunt u elk knooppunt markeren als het start- of initiële knooppunt waar u doorheen wilt gaan. De BFS bezoekt het knooppunt, markeert het als bezocht en plaatst het in de wachtrij.
  2. Nu zal de BFS de Ne bezoekenarest en niet-bezochte knooppunten en markeert deze. Deze waarden worden ook aan de wachtrij toegevoegd. De wachtrij werkt op de FIFO-model.
  3. Op een vergelijkbare manier worden de resterende nearest- en niet-bezochte knooppunten in de grafiek worden geanalyseerd, gemarkeerd en aan de wachtrij toegevoegd. Deze items worden als ontvangst uit de wachtrij verwijderd en als resultaat afgedrukt.

Waarom hebben we het BFS-algoritme nodig?

Er zijn talloze redenen om het BFS-algoritme als zodanig te gebruikenarching voor uw gegevensset. Enkele van de meest essentiële aspecten die dit algoritme tot uw eerste keuze maken, zijn:

  • BFS is handig voor het analyseren van de knooppunten in een grafiek en het construeren van de kortste route om er doorheen te gaan.
  • BFS kan in het kleinste aantal iteraties door een grafiek bladeren.
  • Het archiDe structuur van het BFS-algoritme is eenvoudig en robuust.
  • Het resultaat van het BFS-algoritme heeft een hoog nauwkeurigheidsniveau in vergelijking met andere algoritmen.
  • BFS-iteraties zijn naadloos en er is geen mogelijkheid dat dit algoritme verstrikt raakt in een oneindig lusprobleem.

Hoe werkt het BFS-algoritme?

Voor het doorlopen van grafieken is het nodig dat het algoritme elk afzonderlijk niet-bezocht knooppunt in een boomachtige structuur bezoekt, controleert en/of bijwerkt. Grafiekdoorgangen worden gecategoriseerd op basis van de volgorde waarin ze de knooppunten in de grafiek bezoeken.

Het BFS-algoritme start de bewerking vanaf het eerste of startknooppunt in een grafiek en doorloopt deze grondig. Zodra het met succes het initiële knooppunt heeft doorlopen, wordt het volgende niet-doorkruiste hoekpunt in de grafiek bezocht en gemarkeerd.

Je kunt dus zeggen dat alle knooppunten die aan het huidige hoekpunt grenzen, in de eerste iteratie worden bezocht en doorlopen. Er wordt gebruik gemaakt van een eenvoudige wachtrijmethodologie om de werking van een BFS-algoritme te implementeren, en deze bestaat uit de volgende stappenwing stappen:

Stap 1)

Werking van het BFS-algoritme

Elk hoekpunt of knooppunt in de grafiek is bekend. U kunt het knooppunt bijvoorbeeld markeren als V.

Stap 2)

Werking van het BFS-algoritme

Als het hoekpunt V niet toegankelijk is, voeg dan het hoekpunt V toe aan de BFS-wachtrij

Stap 3)

Werking van het BFS-algoritme

Start de BFS-zoekopdracht en markeer na voltooiing hoekpunt V als bezocht.

Stap 4)

Werking van het BFS-algoritme

De BFS-wachtrij is nog steeds niet leeg. Verwijder daarom het hoekpunt V van de grafiek uit de wachtrij.

Stap 5)

Werking van het BFS-algoritme

Haal alle resterende hoekpunten op de grafiek op die grenzen aan hoekpunt V

Stap 6)

Werking van het BFS-algoritme

Voor elk aangrenzend hoekpunt, laten we zeggen V1, als het nog niet bezocht is, voeg dan V1 toe aan de BFS-wachtrij

Stap 7)

Werking van het BFS-algoritme

BFS zal V1 bezoeken, markeren als bezocht en uit de wachtrij verwijderen.

Voorbeeld BFS-algoritme

Stap 1)

Voorbeeld BFS-algoritme

Je hebt een grafiek met zeven getallen variërend van 0 – 6.

Stap 2)

Voorbeeld BFS-algoritme

0 of nul is gemarkeerd als hoofdknooppunt.

Stap 3)

Voorbeeld BFS-algoritme

0 wordt bezocht, gemarkeerd en ingevoegd in de wachtrijgegevensstructuur.

Stap 4)

Voorbeeld BFS-algoritme

De resterende 0 aangrenzende en niet-bezochte knooppunten worden bezocht, gemarkeerd en in de wachtrij geplaatst.

Stap 5)

Voorbeeld BFS-algoritme

Het doorlopen van iteraties wordt herhaald totdat alle knooppunten zijn bezocht.

Regels van het BFS-algoritme

Hier volgen belangrijke regels voor het gebruik van het BFS-algoritme:

  • Een wachtrij (FIFO-First in First Out) data structuur wordt gebruikt door BFS.
  • U markeert elk knooppunt in de grafiek als wortel en begint de gegevens daaruit te doorzoeken.
  • BFS doorloopt alle knooppunten in de grafiek en blijft ze als voltooid verwijderen.
  • BFS bezoekt een aangrenzend niet-bezocht knooppunt, markeert het als voltooid en voegt het in een wachtrij in.
  • Verwijdert het vorige hoekpunt uit de wachtrij als er geen aangrenzend hoekpunt wordt gevonden.
  • Het BFS-algoritme herhaalt zich totdat alle hoekpunten in de grafiek met succes zijn doorlopen en als voltooid zijn gemarkeerd.
  • Er zijn geen lussen veroorzaakt door BFS tijdens het passeren van gegevens vanaf welk knooppunt dan ook.

Toepassingen van het BFS-algoritme

Laten we eens kijken naar enkele van de real-life toepassingen waarbij een BFS-algoritme-implementatie zeer effectief kan zijn.

  • Ongewogen grafieken: Het BFS-algoritme kan eenvoudig het kortste pad en een minimaal opspannende boom creëren om alle hoekpunten van de grafiek in de kortst mogelijke tijd en met hoge nauwkeurigheid te bezoeken.
  • P2P-netwerken: BFS kan worden geïmplementeerd om alle nieuwe te lokaliserenarest of aangrenzende knooppunten in een peer-to-peer-netwerk. Hierdoor worden de benodigde gegevens sneller gevonden.
  • Webcrawlers: Zoekmachines of webcrawlers kunnen eenvoudig meerdere indexniveaus opbouwen door gebruik te maken van BFS. De BFS-implementatie begint bij de bron, namelijk de webpagina, en bezoekt vervolgens alle links van die bron.
  • Navigatiesystemen: BFS kan helpen bij het vinden van alle aangrenzende locaties vanaf de hoofd- of bronlocatie.
  • Netwerkuitzending: Een uitgezonden pakket wordt door het BFS-algoritme geleid om alle knooppunten waarvoor het een adres heeft, te vinden en te bereiken.

Samengevat

  • Het doorlopen van een grafiek is een uniek proces waarbij het algoritme elk afzonderlijk niet-bezocht knooppunt in een boomachtige structuur moet bezoeken, controleren en/of bijwerken. Het BFS-algoritme werkt volgens een soortgelijk principe.
  • Het algoritme is nuttig voor het analyseren van de knooppunten in een grafiek en het construeren van de kortste route om er doorheen te gaan.
  • Het algoritme doorloopt de grafiek in het kleinste aantal iteraties en in de kortst mogelijke tijd.
  • BFS selecteert een enkel knooppunt (begin- of bronpunt) in een grafiek en bezoekt vervolgens alle knooppunten die grenzen aan het geselecteerde knooppunt. BFS heeft één voor één toegang tot deze knooppunten.
  • De bezochte en gemarkeerde gegevens worden door BFS in een wachtrij geplaatst. Een wachtrij werkt op basis van 'first in, first out'. Het element dat als eerste in de grafiek is geplaatst, wordt dus als eerste verwijderd en als resultaat afgedrukt.
  • Het BFS-algoritme kan nooit in een oneindige lus terechtkomen.
  • Vanwege de hoge nauwkeurigheid en robuuste implementatie wordt BFS gebruikt in meerdere real-life oplossingen zoals P2P-netwerken, webcrawlers en netwerkuitzendingen.