BFS versus DFS – het verschil daartussen

Wat is BFS?

BFS is een algoritme dat wordt gebruikt om gegevens grafisch weer te geven of om bomen te doorzoeken of structuren te doorkruisen. Het algoritme bezoekt en markeert efficiënt alle belangrijke knooppunten in een grafiek op een nauwkeurige breedtewijze.

Dit algoritme selecteert een enkel knooppunt (begin- of bronpunt) in een grafiek en bezoekt vervolgens alle knooppunten die grenzen aan het geselecteerde knooppunt. Zodra het algoritme het startknooppunt bezoekt en markeert, beweegt het naar de dichtstbijzijnde niet-bezochte 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. De volledige vorm van BFS is de breedte-eerst-zoekopdracht.

Wat is DFS?

DFS is een algoritme voor het vinden of doorkruisen van grafieken of bomen in diepterichting. De uitvoering van het algoritme begint bij het hoofdknooppunt en onderzoekt elke tak voordat het teruggaat. Het maakt gebruik van een stapelgegevensstructuur om te onthouden, om het volgende hoekpunt te verkrijgen en om een ​​zoekopdracht te starten wanneer er in een iteratie een doodlopende weg verschijnt. De volledige vorm van DFS is Diepte-eerst zoeken.

Verschil tussen BFS en DFS binaire boom

Dit zijn de belangrijke verschillen tussen BFS en DFS.

BFS	DFS
BFS vindt de kortste weg naar de bestemming.	DFS gaat naar het einde van een substructuur en gaat vervolgens terug.
De volledige vorm van BFS is Breadth-First Search.	De volledige vorm van DFS is Depth First Search.
Het maakt gebruik van een wachtrij om de volgende te bezoeken locatie bij te houden.	Het maakt gebruik van een stapel om bij te houden welke volgende locatie moet worden bezocht.
BFS doorloopt volgens boomniveau.	DFS doorkruist op basis van de boomdiepte.
Het wordt geïmplementeerd met behulp van de FIFO-lijst.	Het wordt geïmplementeerd met behulp van de LIFO-lijst.
Het vereist meer geheugen in vergelijking met DFS.	Het vereist minder geheugen in vergelijking met BFS.
Dit algoritme geeft de ondiepste padoplossing.	Dit algoritme garandeert niet de ondiepste padoplossing.
Er is geen noodzaak om terug te gaan in BFS.	Er is behoefte aan een backtracking in DFS.
Je kunt nooit gevangen zitten in eindige lussen.	Je kunt gevangen zitten in oneindige lussen.
Als u geen enkel doel vindt, moet u mogelijk veel knooppunten uitbreiden voordat de oplossing wordt gevonden.	Als u geen enkel doel vindt, kan het teruglopen van het bladknooppunt optreden.

Voorbeeld van BFS

In het volgende BFS-voorbeeld hebben we een grafiek met 6 hoekpunten gebruikt.

Voorbeeld van BFS

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.

Voorbeeld van DFS

In het volgende DFS-voorbeeld hebben we een ongerichte grafiek met 5 hoekpunten gebruikt.

Stap 1)

We zijn begonnen bij hoekpunt 0. Het algoritme begint door het in de bezochte lijst te plaatsen en tegelijkertijd alle aangrenzende hoekpunten in de data structuur stapel genoemd.

Stap 2)

Je bezoekt het element dat bovenaan de stapel staat, bijvoorbeeld 1, en gaat naar de aangrenzende knooppunten. Het is omdat 0 al bezocht is. Daarom bezoeken we hoekpunt 2.

Stap 3)

Hoekpunt 2 heeft een niet bezocht nabijgelegen hoekpunt in 4. Daarom voegen we dat toe aan de stapel en bezoeken het.

Stap 4)

Ten slotte zullen we het laatste hoekpunt 3 bezoeken, dit heeft geen onbezochte aangrenzende knooppunten. We hebben het doorlopen van de grafiek voltooid met behulp van het DFS-algoritme.

Toepassingen van BFS

Hier zijn toepassingen van BFS:

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 bouwen door BFS te gebruiken. De BFS-implementatie begint bij de bron, namelijk de webpagina, en bezoekt vervolgens alle links van die bron.

Netwerkuitzending

Een uitgezonden pakket wordt door het BFS-algoritme geleid om alle knooppunten waarvoor het een adres heeft, te vinden en te bereiken.

Toepassingen van DFS

Hier zijn belangrijke toepassingen van DFS:

Gewogen grafiek

In een gewogen grafiek genereert het doorlopen van de DFS-grafiek de kortste padboom en de minimaal opspannende boom.

Een cyclus in een grafiek detecteren

Een grafiek heeft een cyclus als we tijdens DFS een achterrand vinden. Daarom moeten we DFS uitvoeren voor de grafiek en controleren op achterranden.

Padvinden

We kunnen ons specialiseren in het DFS-algoritme om een ​​pad tussen twee hoekpunten te zoeken.

Topologische sortering

Het wordt voornamelijk gebruikt voor het plannen van taken van de gegeven afhankelijkheden binnen de groep taken. In de computerwetenschap wordt het gebruikt bij het plannen van instructies, dataserialisatie, logische synthese en het bepalen van de volgorde van compilatietaken.

Zoeken naar sterk verbonden componenten van een grafiek

Het wordt gebruikt in de DFS-grafiek wanneer er een pad is van elk hoekpunt in de grafiek naar andere resterende hoekpunten.

Puzzels oplossen met slechts één oplossing

Het DFS-algoritme kan eenvoudig worden aangepast om alle oplossingen voor een doolhof te zoeken door knooppunten op het bestaande pad in de bezochte set op te nemen.