BFS versus DFS: ken het verschil

Wat is BFS ?

BFS is een algoritme dat wordt gebruikt om grafieken van gegevens te maken of om boom- of doorkruisstructuren te doorzoeken. Het algoritme bezoekt en markeert efficiënt alle belangrijke knooppunten in een grafiek op een nauwkeurige wijze in de breedte.

Dit algoritme selecteert een enkel knooppunt (beginpunt of bronpunt) in een grafiek en bezoekt vervolgens alle knooppunten grenzend aan het geselecteerde knooppunt. Zodra het algoritme het startknooppunt bezoekt en markeert, gaat het naar de dichtstbijzijnde niet-bezochte knooppunten en analyseert het deze.

Eenmaal bezocht, zijn 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-eerste zoekopdracht.

In deze BSF Vs. DFS Binary tree tutorial, u zult leren:

• Wat is BFS?
• Wat is DFS?
• Voorbeeld van BFS
• Voorbeeld van DFS
• Verschil tussen BFS en DFS binaire structuur
• Toepassingen van BFS
• Toepassingen van DFS

Wat is DFS?

DFS is een algoritme voor het zoeken naar of doorlopen van grafieken of bomen in de diepte. De uitvoering van het algoritme begint bij het hoofdknooppunt en verkent elke vertakking alvorens terug te volgen. Het gebruikt een stapel datastructuur 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 Diepte-eerst zoeken.

Voorbeeld van BFS

In het volgende voorbeeld van DFS hebben 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 is bezocht, gemarkeerd , en ingevoegd in de datastructuur van de wachtrij.

Stap 4)

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

Stap 5)

Herhalende iteraties worden herhaald totdat alle knooppunten zijn bezocht.

Voorbeeld van DFS

In het volgende voorbeeld van DFS hebben we een niet-gerichte graaf gebruikt met 5 hoekpunten.

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 gegevens te plaatsen structuur genaamd stapel.

Stap 2)

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

Stap 3)

Vertex 2 heeft een onbezochte nabije vertex in 4. Daarom voegen we dat toe aan de stapel en bezoeken het.

Stap 4)

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

Verschil tussen BFS en DFS binaire structuur

BFS	DFS
BFS vindt het kortste pad naar de bestemming.	DFS gaat naar de onderkant van een substructuur en loopt 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 doorkruist volgens boomniveau.	DFS doorkruist volgens boomdiepte.
Het wordt geïmplementeerd met FI FO 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 meest ondiepe padoplossing.	Dit algoritme garandeert niet de meest ondiepe padoplossing.
Er is geen behoefte aan backtracking in BFS.	Er is een behoefte aan backtracking in DFS.
Je kunt nooit in eindige lussen worden opgesloten.	Je kunt in oneindige lussen worden opgesloten.
Als u geen doel vindt, moet u mogelijk veel knooppunten uitbreiden voordat de oplossing is gevonden.	Als u geen doel vindt, kan het bladknooppunt teruggaan optreden.

Applicaties van BFS

Hier zijn applicaties van BFS:

Ongewogen Grafieken:

BFS-algoritme kan gemakkelijk het kortste pad en een minimale spanning tree 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 naburige knooppunten in een peer-to-peer-netwerk te lokaliseren. Dit zal de vereiste gegevens sneller vinden.

Webcrawlers:

Zoekmachines of webcrawlers kunnen gemakkelijk meerdere niveaus van indexen bouwen door BFS te gebruiken. De implementatie van BFS 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 minimale spanning tree.

Een cyclus in een grafiek detecteren:

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

Path Finding:

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

Zoeken naar sterk verbonden componenten van een grafiek:

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

Puzzels oplossen met slechts één oplossing:

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