BFS versus DFS: ken het verschil

Wat is BFS?

BFS is een algoritme dat wordt gebruikt om gegevens in een grafiek uit te zetten of om in boom- of doorkruisende structuren te zoeken. Het algoritme bezoekt en markeert op efficiënte wijze alle belangrijke knooppunten in een grafiek in een nauwkeurige breedte.

Dit algoritme selecteert een enkel knooppunt (beginpunt of bronpunt) in een grafiek en bezoekt vervolgens alle knooppunten naast het geselecteerde knooppunt. Zodra het algoritme het startknooppunt bezoekt en markeert, gaat 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 Breadth-first search.

In deze BSF Vs. DFS Binary tree tutorial, je leert:

Wat is DFS?

DFS is een algoritme voor het vinden of doorkruisen van grafieken of bomen in dieptewaartse richting. De uitvoering van het algoritme begint bij het hoofdknooppunt en verkent elke vertakking voordat het teruggaat. Het gebruikt een stapelgegevensstructuur om te onthouden, om het volgende hoekpunt te krijgen en om een ​​zoekopdracht te starten wanneer er een doodlopende weg in een iteratie verschijnt. De volledige vorm van DFS is Depth-first search.

Voorbeeld van BFS

In het volgende voorbeeld van DFS hebben we een grafiek met 6 hoekpunten gebruikt.

Voorbeeld van BFS

Stap 1)

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

Stap 2)

0 of nul is gemarkeerd als een hoofdknooppunt.

Stap 3)

0 wordt bezocht, gemarkeerd en ingevoegd in de wachtrijgegevensstructuur.

Stap 4)

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

Stap 5)

Doorlopende iteraties worden herhaald totdat alle knooppunten zijn bezocht.

Voorbeeld van DFS

In het volgende voorbeeld van DFS hebben we een ongerichte graaf met 5 hoekpunten gebruikt.

Stap 1)

We zijn begonnen vanaf hoekpunt 0. Het algoritme begint door het in de bezochte lijst te plaatsen en tegelijkertijd alle aangrenzende hoekpunten in de gegevensstructuur genaamd stapel te plaatsen.

Stap 2)

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

Stap 3)

Vertex 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, het heeft geen niet-bezochte aangrenzende knooppunten. We hebben de doorloop van de grafiek voltooid met behulp van het DFS-algoritme.

Verschil tussen BFS en DFS binaire boom

BFS DFS
BFS vindt het kortste pad naar de bestemming.DFS gaat naar de onderkant van een substructuur en gaat dan terug.
De volledige vorm van BFS is Breadth-First Search.De volledige vorm van DFS is Depth First Search.
Het gebruikt een wachtrij om de volgende te bezoeken locatie bij te houden.Het gebruikt een stapel om de volgende te bezoeken locatie bij te houden.
BFS doorloopt op boomniveau.DFS doorloopt volgens 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 meest ondiepe padoplossing.
Het is niet nodig om terug te gaan in BFS.Er is behoefte aan backtracking in DFS.
Je kunt nooit vast komen te zitten in eindige lussen.Je kunt vast komen te zitten in oneindige lussen.
Als u geen doel vindt, moet u mogelijk veel knooppunten uitbreiden voordat de oplossing is gevonden.Als u geen doel vindt, kan het terugtrekken van de bladknooppunten plaatsvinden.

Toepassingen van BFS

Hier zijn toepassingen van BFS:

Niet-gewogen grafieken:

Het BFS-algoritme kan gemakkelijk het kortste pad en een minimale opspannende boom creëren om alle hoekpunten van de grafiek in de kortst mogelijke tijd met hoge nauwkeurigheid te bezoeken.

P2P-netwerken:

BFS kan worden geïmplementeerd om alle dichtstbijzijnde of aangrenzende knooppunten in een peer-to-peer-netwerk te lokaliseren. Zo vindt u sneller de benodigde gegevens.

Webcrawlers:

Zoekmachines of webcrawlers kunnen eenvoudig meerdere niveaus van indexen bouwen door BFS te gebruiken. BFS-implementatie begint bij de bron, de webpagina, en bezoekt vervolgens alle links van die bron.

Netwerkuitzending:

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

Toepassingen van DFS

Hier zijn belangrijke toepassingen van DFS:

Gewogen grafiek:

In een gewogen grafiek genereert DFS-grafiektraversal de kortste padboom en de minimaal opspannende boom.

Een cyclus detecteren in een grafiek:

Een grafiek heeft een cyclus als we tijdens DFS een achterrand hebben gevonden. Daarom moeten we DFS voor de grafiek uitvoeren 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 informatica wordt het gebruikt bij het plannen van instructies, gegevensserialisatie, 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 doorzoeken door knooppunten op het bestaande pad in de bezochte set op te nemen.

BELANGRIJKSTE VERSCHILLEN:

  • BFS vindt het kortste pad naar de bestemming, terwijl DFS naar de onderkant van een substructuur gaat en dan 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 de volgende te bezoeken locatie bij te houden. terwijl DFS een stapel gebruikt om de volgende te bezoeken locatie bij te houden.
  • BFS doorloopt volgens boomniveau terwijl DFS doorloopt volgens boomdiepte.
  • BFS wordt geïmplementeerd met behulp van de FIFO-lijst, terwijl DFS wordt geïmplementeerd met behulp van de LIFO-lijst.
  • In BFS kun je nooit vast komen te zitten in eindige lussen, terwijl je in DFS vast kunt zitten in oneindige lussen.