Wat is BFS?
BFS is een algoritme dat wordt gebruikt om gegevens in een grafiek te plaatsen 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 naast het geselecteerde knooppunt. Zodra het algoritme het startknooppunt bezoekt en markeert, beweegt het zich 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-zelfstudie, u leert:
- Wat is BFS?
- Wat is DFS?
- Voorbeeld van BFS
- Voorbeeld van DFS
- Verschil tussen BFS en DFS Binary Tree
- 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 verschijnt in een iteratie. De volledige vorm van DFS is Diepte-eerst zoeken.
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 datastructuur van de wachtrij.
Stap 4)
De 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 ongerichte 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 datastructuur genaamd stapel te plaatsen.
Stap 2)
Je bezoekt het element, dat zich bijvoorbeeld bovenaan de stapel bevindt, 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 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, het heeft geen onbezochte aangrenzende knooppunten. We hebben het doorlopen van de grafiek voltooid met behulp van het DFS-algoritme.
Verschil tussen BFS en DFS Binary Tree
| 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 maakt gebruik van 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 volgens 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 meest ondiepe padoplossing. | Dit algoritme garandeert niet de meest ondiepe padoplossing. |
| Backtracking in BFS is niet nodig. | Er is behoefte aan backtracking in DFS. |
| Je kunt nooit vast komen te zitten in eindige lussen. | Je kunt worden opgesloten 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 de backtracking van de leaf-node optreden. |
Toepassingen van BFS
Hier zijn toepassingen van BFS:
Ongewogen grafieken:
Het BFS-algoritme kan eenvoudig 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 aangrenzende knooppunten in een peer-to-peer-netwerk te lokaliseren. Dit zal de vereiste gegevens sneller vinden.
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 graph traversal de kortste padboom en de minimum spanning tree.
Een cyclus in een grafiek detecteren:
Een grafiek heeft een cyclus als we tijdens DFS een achterrand hebben gevonden. 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 tussen de groep taken. In de informatica wordt het gebruikt bij instructieplanning, dataserialisatie, logische synthese, het bepalen van de volgorde van compilatietaken.
Sterk verbonden componenten van een grafiek zoeken:
Het wordt gebruikt in de DFS-grafiek als 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 vervolgens terugloopt.
- 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 doorkruist volgens boomniveau terwijl DFS doorkruist volgens boomdiepte.
- BFS wordt geïmplementeerd met behulp van de FIFO-lijst, aan de andere kant wordt DFS geïmplementeerd met behulp van de LIFO-lijst.
- In BFS kun je nooit in eindige lussen terechtkomen, terwijl je in DFS in oneindige lussen terecht kunt komen.