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 grafisch weer te geven of om bomen of structuren te doorzoeken. De volledige vorm van BFS is Breadth-first search.

Het algoritme bezoekt en markeert efficiënt alle belangrijke knooppunten in een grafiek op een nauwkeurige breedtewijze. Dit algoritme selecteert een enkel knooppunt (initieel of bronpunt) in een grafiek en bezoekt vervolgens alle knooppunten die grenzen aan het geselecteerde knooppunt. Vergeet niet dat BFS deze knooppunten één voor één benadert.

Zodra het algoritme het startknooppunt bezoekt en markeert, beweegt het naar de dichtstbijzijnde niet-bezochte knooppunten en analyseert deze. Zodra bezocht, worden alle knooppunten gemarkeerd. Deze iteraties gaan door totdat alle knooppunten van de grafiek succesvol 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.

De 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 dichtstbijzijnde en niet-bezochte knooppunten bezoeken en deze markeren. Deze waarden worden ook aan de wachtrij toegevoegd. De wachtrij werkt op de FIFO-model.
3. Op een vergelijkbare manier worden de resterende dichtstbijzijnde en niet-bezochte knooppunten op de grafiek geanalyseerd, gemarkeerd en toegevoegd aan de wachtrij. Deze items worden uit de wachtrij verwijderd als ontvangen en afgedrukt als het resultaat.

Waarom hebben we het BFS-algoritme nodig?

Er zijn talloze redenen om het BFS-algoritme te gebruiken als zoekfunctie voor uw dataset. Enkele van de meest vitale aspecten die dit algoritme 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.
• De architectuur van het BFS-algoritme is eenvoudig en robuust.
• Het resultaat van het BFS-algoritme is zeer nauwkeurig vergeleken 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.

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

Daarom kun je zeggen dat alle knooppunten die grenzen aan de huidige vertex worden bezocht en doorkruist in de eerste iteratie. Een eenvoudige wachtrijmethodologie wordt gebruikt om de werking van een BFS-algoritme te implementeren en bestaat uit de volgende stappen:

Stap 1)

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

Stap 2)

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

Stap 3)

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

Stap 4)

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

Stap 5)

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

Stap 6)

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

Stap 7)

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

Voorbeeld BFS-algoritme

Stap 1)

Je hebt een grafiek met zeven getallen van 0 tot en met 6.

Stap 2)

0 of nul is gemarkeerd als hoofdknooppunt.

Stap 3)

0 wordt bezocht, gemarkeerd en ingevoegd in de wachtrijgegevensstructuur.

Stap 4)

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

Stap 5)

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 dichtstbijzijnde of aangrenzende knooppunten in een peer-to-peernetwerk te lokaliseren. Dit zal de vereiste gegevens sneller vinden.
• 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.

Samenvatting

• 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.