Breadth First Search (BFS)-algoritme met VOORBEELD
Sara Chen
⚡ Slimme samenvatting
Breadth First Search (BFS) is een algoritme dat een graaf niveau voor niveau doorloopt en alle buren van een knooppunt bezoekt voordat het dieper gaat. Het maakt gebruik van een FIFO-wachtrij en vindt het kortste pad in ongewogen grafen zonder oneindige lussen.
Wat is BFS-algoritme (Breadth-First Search)?
Breedte-eerst zoeken (BFS) is een algoritme dat wordt gebruikt om gegevens in grafieken weer te geven, een boomstructuur te doorzoeken of structuren te doorlopen. De volledige naam van BFS is breedte-eerst zoeken.
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
- Op de verschillende niveaus van de data kun je elk knooppunt markeren als start- of beginknooppunt om de doorloop te starten. De BFS bezoekt het knooppunt, markeert het als bezocht en plaatst het in de wachtrij.
- Nu zal BFS de dichtstbijzijnde en nog niet bezochte knooppunten bezoeken en markeren. Deze waarden worden ook aan de wachtrij toegevoegd. De wachtrij werkt op basis van de FIFO-model.
- Op dezelfde manier worden de resterende dichtstbijzijnde en nog niet bezochte knooppunten in de grafiek geanalyseerd, gemarkeerd en aan de wachtrij toegevoegd. Deze items worden uit de wachtrij verwijderd zodra ze binnenkomen en als resultaat worden afgedrukt.
Waarom hebben we het BFS-algoritme nodig?
Er zijn talloze redenen om het BFS-algoritme te gebruiken voor het doorzoeken van je dataset. Enkele van de belangrijkste aspecten die dit algoritme tot je 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.
Je kunt dus stellen dat alle knooppunten die grenzen aan het huidige knooppunt in de eerste iteratie worden bezocht en doorlopen. Een eenvoudige wachtrijmethode wordt gebruikt om de werking van een BFS-algoritme te implementeren, en deze 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 knooppunt V niet wordt benaderd, voeg knooppunt V dan toe aan de BFS-wachtrij.
Stap 3)
Start de BFS-zoektocht en markeer na voltooiing knooppunt 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 in de graaf die grenzen aan hoekpunt V.
Stap 6)
Voor elke aangrenzende knoop, laten we zeggen V1, voeg je V1 toe aan de BFS-wachtrij als deze nog niet bezocht is.
Stap 7)
BFS bezoekt V1, markeert deze als bezocht en verwijdert deze uit de wachtrij.
Voorbeeld BFS-algoritme
Stap 1)
Je hebt een grafiek met zeven getallen van 0 tot 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 knooppunten die direct grenzen aan 0 en nog niet bezocht zijn, 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
Hieronder volgen belangrijke regels voor het gebruik van het BFS-algoritme:
- Een wachtrij (FIFO – First In First Out) data structuur wordt gebruikt door BFS.
- Je markeert een willekeurig knooppunt in de grafiek als de wortel en begint vanaf dat punt de gegevens te doorlopen.
- BFS doorloopt alle knooppunten in de grafiek en laat ze vallen.ping als voltooid.
- BFS bezoekt een aangrenzend niet-bezocht knooppunt, markeert het als voltooid en voegt het in een wachtrij in.
- Het verwijdert het vorige knooppunt uit de wachtrij als er geen aangrenzend knooppunt wordt gevonden.
- Het BFS-algoritme herhaalt zich totdat alle knooppunten in de graaf succesvol 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 minimale opspannende boom creëren om alle knooppunten van de graaf in de kortst mogelijke tijd met hoge nauwkeurigheid te bezoeken.
- P2P-netwerken: BFS kan worden gebruikt om alle dichtstbijzijnde of naburige knooppunten in een peer-to-peer-netwerk te lokaliseren. 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.
