Verschil tussen BFS versus DFS
Breadth-First Search (BFS) en Depth First Search (DFS) zijn twee belangrijke algoritmen die worden gebruikt voor het zoeken. Breadth-First Search start zijn zoekactie vanaf het eerste knooppunt en beweegt vervolgens over de niveaus die dichter bij het rootknooppunt liggen, terwijl het Depth First Search-algoritme begint met het eerste knooppunt en vervolgens zijn pad voltooit naar het eindknooppunt van het respectieve pad. Beide algoritmen doorlopen elk knooppunt tijdens het zoeken. Verschillende codes worden geschreven voor de twee algoritmen om het proces van doorlopen uit te voeren. Ze worden ook beschouwd als belangrijke zoekalgoritmen in kunstmatige intelligentie.
In dit onderwerp gaan we meer te weten komen over BFS VS DFS.
Hoe BFS en DFS werken?
Het werkingsmechanisme van beide algoritmen wordt hieronder met voorbeelden uitgelegd. Raadpleeg deze voor een beter begrip van de gebruikte aanpak.
Breedte-eerste zoekvoorbeeld
- Stap 1: N1 is het root-knooppunt, dus het begint vanaf hier. N1 is verbonden met drie knooppunten N2, N3 en N4. Alle drie knooppunten zijn nog niet bezocht. We starten dus vanaf N2 en slaan het op in de wachtrij. Dus de wachtrij met de naam Q bevat alleen N2.
Vraag: N2
- Stap 2: Vervolgens is het knooppunt dat is verbonden met N1 N3. Omdat we het knooppunt zijn tegengekomen of hebben bezocht, slaan we het op in de wachtrij. Dus de bijgewerkte wachtrij is
Vraag: N3, N2
- Stap 3: Vervolgens is het knooppunt dat is verbonden met het hoofdknooppunt N4. We zullen het in de wachtrij opslaan.
Vraag: N4, N3, N2
- Stap 4: Alle knooppunten die zijn verbonden met N1 worden opgeslagen in de wachtrij. Nu verwijderen we N2 uit de wachtrij volgens het First in First Out-principe (FIFO) en vinden we de knooppunten die zijn verbonden met de N2, dwz N5. N5 wordt niet één keer bezocht, dus we zullen het in de wachtrij opslaan.
Vraag: N5, N4, N3
- Stap 5: Alle hoekpunten worden bezocht, dus we blijven de knooppunten uit de wachtrij verwijderen totdat deze leeg is.
Diepte Eerste zoekvoorbeeld
- Stap 1: We beginnen met N1 als het startknooppunt en slaan het op in een stapel S. N1 is verbonden met drie aangrenzende knooppunten N2, N3 en N4. Beginnend met N2 (u kunt alfabetisch of numeriek beginnen), zullen we dit in de stapel plaatsen.
S: N2 (boven), N1
- Stap 2: Nu zijn de aangrenzende knooppunten van N2 N1 en N5. Omdat N1 al in de stapel aanwezig is, betekent dit dat deze wordt bezocht, dus nemen we N5 en plaatsen we deze in de stapel S.
S: N5 (boven), N2, N1
- Stap 3: Nu zijn de aangrenzende knooppunten van N5 N3 en N4. We beginnen zal N3 en zet het in de stapel.
S: N3 (boven), N5, N2, N1
Nu is N3 verbonden met N5 en N1 die al in de stapel aanwezig zijn, wat betekent dat ze worden bezocht, dus zullen we N3 uit de stapel verwijderen volgens het principe LIFO (Last in First Out).
S: N5 (boven), N2, N1
- Stap 4: Nu zullen we het laatste knooppunt plaatsen dat we niet zijn tegengekomen in de hele verplaatsing in N4 en het in de stapel plaatsen.
S: N4 (boven), N5, N2, N1
- Stap 5: Nu worden we niet weggelaten door andere knooppunten, dus we zullen in de stapel controleren of er knooppunten zijn aangesloten op de respectieve knooppunten die erin aanwezig zijn en die niet worden bezocht. Als alle verbonden knooppunten worden bezocht, verwijderen we de aanwezige knooppunten in de stapel. N4 heeft bijvoorbeeld geen verbindingsknooppunten die we niet hebben gecontroleerd, dus we zullen het van de stapel verwijderen. Op dezelfde manier kunnen we controleren op andere knooppunten. Het algoritme stopt zodra de stapel leeg is.
Head to Head-vergelijking tussen BFS versus DFS (infographics)
Hieronder staan de top 6 verschillen tussen BFS VS DFS
Belangrijkste verschillen tussen BFS en DFS
Laten we enkele van de belangrijkste belangrijkste verschillen tussen BFS en DFS bespreken
- Breadth-First Search (BFS) start vanaf het hoofdknooppunt en bezoekt alle bijbehorende knooppunten terwijl DFS start vanaf het hoofdknooppunt en het volledige pad voltooit dat aan het knooppunt is gekoppeld.
- BFS volgt de benadering van Queue terwijl DFS de benadering van Stack volgt.
- De aanpak die wordt gebruikt in BFS is optimaal, terwijl het proces dat wordt gebruikt in DFS niet optimaal is.
- Als ons doel is om het kortste pad te vinden, heeft BFS de voorkeur boven DFS.
BFS en DFS-vergelijkingstabel
Laten we de topvergelijking tussen BFS versus DFS bespreken
| BFS | DFS |
| De volledige vorm van BFS is Breadth-First Search. | De volledige vorm van DFS is Depth First Search |
| BFS is bedoeld om de kortste afstand te vinden en het begint bij het eerste of root-knooppunt en beweegt over alle knooppunten die aan de respectieve knooppunten zijn bevestigd. U kunt een duidelijk beeld krijgen van het werkingsmechanisme nadat u het onderstaande voorbeeld hebt doorgenomen. | DFS volgt een op diepte gebaseerde benadering en voltooit het volledige pad door alle knooppunten die aan het respectieve knooppunt zijn gekoppeld. U kunt een duidelijk beeld krijgen van het werkingsmechanisme nadat u het onderstaande voorbeeld hebt doorgenomen. |
| Dit gebeurt volgens het Queue-principe, de First In First Out-benadering (FIFO). | Het wordt gedaan met behulp van het Stack-principe, wat de Last In First out-benadering (LIFO) is. |
| De knooppunten die meer dan eens worden doorlopen, worden uit de wachtrij verwijderd. | De bezochte knooppunten worden in de stapel ingevoegd en worden later verwijderd als er geen knooppunten meer zijn om te bezoeken. |
| Het is relatief langzamer dan Depth First Search. | Het is sneller dan het Breadth-First Search-algoritme. |
| Geheugentoewijzing is meer dan het Depth First Search-algoritme. | Geheugentoewijzing is relatief minder dan het Breadth-First Search-algoritme |
Conclusie
Er zijn veel toepassingen waarbij de bovenstaande algoritmen worden gebruikt als machine learning of om kunstmatige intelligentie-gerelateerde oplossingen enz. Te vinden. Ze worden voornamelijk gebruikt in grafieken om te bepalen of het al dan niet tweepartig is, om cycli of componenten te detecteren die verbonden zijn. Ze worden ook beschouwd als belangrijke algoritmen om het pad te vinden of om de kortste afstand te vinden. Afhankelijk van de behoeften van het bedrijf kunnen we twee algoritmen gebruiken. Breadth-First Search wordt echter beschouwd als een optimale manier in plaats van het Depth First Search-algoritme.
Aanbevolen artikelen
Dit is een handleiding voor BFS VS DFS. Hier bespreken we de BFS VS DFS belangrijkste verschillen met infographics en vergelijkingstabel. U kunt ook de volgende artikelen bekijken voor meer informatie -
- BFS-algoritme
- TeraData versus Oracle
- Big Data versus Data Warehouse
- Big Data vs Apache Hadoop: Top 4-vergelijking die u moet leren