BFS versus DFS – het verschil daartussen

Belangrijkste verschil tussen BFS en DFS

  • BFS vindt het kortste pad naar de bestemming, terwijl DFS naar de onderkant van een subboom gaat en vervolgens teruggaat.
  • De volledige vorm van BFS is Breadth-First Search, terwijl de volledige vorm van DFS Depth-First Search is.
  • BFS gebruikt een wachtrij om bij te houden welke volgende locatie bezocht moet worden. terwijl DFS een stapel gebruikt om de volgende te bezoeken locatie bij te houden.
  • BFS doorkruist op basis van boomniveau, terwijl DFS doorkruist op basis van boomdiepte.
  • BFS wordt geïmplementeerd met behulp van een FIFO-lijst; aan de andere kant wordt DFS geïmplementeerd met behulp van een LIFO-lijst.
  • In BFS kun je nooit vastzitten in eindige lussen, terwijl je in DFS vast kunt komen te zitten in oneindige lussen.
Verschil tussen BFS en DFS
Verschil tussen BFS en DFS

Wat is BFS?

BFS is een algoritme dat wordt gebruikt om gegevens of searchidoor bomen heen te gaan of structuren te doorkruisen. 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. 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. 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 vervolgwing voorbeeld van BFS, we hebben een grafiek met 6 hoekpunten gebruikt.

Voorbeeld van BFS

Stap 1)

Voorbeeld van BFS

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

Stap 2)

Voorbeeld van BFS

0 of nul is gemarkeerd als hoofdknooppunt.

Stap 3)

Voorbeeld van BFS

0 wordt bezocht, gemarkeerd en ingevoegd in de wachtrijgegevensstructuur.

Stap 4)

Voorbeeld van BFS

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

Stap 5)

Voorbeeld van BFS

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

Voorbeeld van DFS

In het vervolgwing In het voorbeeld van DFS hebben we een ongerichte grafiek met 5 hoekpunten gebruikt.

Voorbeeld van DFS

Stap 1)

Voorbeeld van DFS

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

Stap 2)

Voorbeeld van DFS

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)

Voorbeeld van DFS

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

Stap 4)

Voorbeeld van DFS

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.

Voorbeeld van DFS

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 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 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 op basis van de gegeven afhankelijkheden binnen de groep taken. In de computerwetenschappen wordt het gebruikt bij instructieplanning, dataserialisatie, logische synthese en het bepalen van de volgorde van compilatietaken.

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