Vad är BFS?
BFS är en algoritm som används för att rita data eller söka i träd eller genomkorsande strukturer. Algoritmen besöker och markerar alla nyckelnoder effektivt i ett diagram på ett korrekt sätt på bredden.
Denna algoritm väljer en enda nod (initial- eller källpunkt) i ett diagram och besöker sedan alla noder intill den valda noden. När algoritmen besöker och markerar startnoden flyttas den mot närmaste oviserade noder och analyserar dem.
Efter att ha besökt markeras alla noder. Dessa iterationer fortsätter tills alla noder i diagrammet har besökts och markerats. Den fullständiga formen av BFS är den bredaste sökningen.
I detta BSF Vs. DFS Binary Tree tutorial, du lär dig:
- Vad är BFS?
- Vad är DFS?
- Exempel på BFS
- Exempel på DFS
- Skillnad mellan BFS och DFS Binary Tree
- Tillämpningar av BFS
- Tillämpningar av DFS
Vad är DFS?
DFS är en algoritm för att hitta eller korsa grafer eller träd i djupgående riktning. Körningen av algoritmen börjar vid rotnoden och utforskar varje gren innan backtracking. Den använder en stapeldatastruktur för att komma ihåg, för att få efterföljande toppunkt och för att starta en sökning, när en återvändsgränd dyker upp i någon iteration. Den fullständiga formen av DFS är Djup-första sökning.
Exempel på BFS
I följande exempel på DFS har vi använt diagram med 6 hörn.
Exempel på BFS
Steg 1)
Du har en graf med sju nummer som sträcker sig från 0 - 6.
Steg 2)
0 eller noll har markerats som en rotnod.
Steg 3)
0 besöks, markeras och infogas i ködatastrukturen.
Steg 4)
Återstående 0 intilliggande och obesökta noder besöks, markeras och infogas i kön.
Steg 5)
Korsande iterationer upprepas tills alla noder besöks.
Exempel på DFS
I följande exempel på DFS har vi använt en oriktad graf med fem hörn.
Steg 1)
Vi har börjat från vertex 0. Algoritmen börjar med att placera den i den besökta listan och samtidigt placera alla dess intilliggande hörn i datastrukturen som kallas stack.
Steg 2)
Du kommer att besöka elementet, som är högst upp i stacken, till exempel 1 och gå till dess intilliggande noder. Det beror på att 0 redan har besökts. Därför besöker vi toppunkt 2.
Steg 3)
Vertex 2 har ett obesökt närliggande toppunkt i 4. Därför lägger vi till det i stacken och besöker det.
Steg 4)
Slutligen kommer vi att besöka den sista toppunkten 3, den har inga oönskade angränsande noder. Vi har slutfört grafens genomgång med DFS-algoritm.
Skillnad mellan BFS och DFS Binary Tree
| BFS | DFS |
| BFS hittar den kortaste vägen till destinationen. | DFS går till botten av ett subtree och sedan backtracks. |
| Den fullständiga formen av BFS är Breadth-First Search. | Den fullständiga formen av DFS är Depth First Search. |
| Den använder en kö för att hålla reda på nästa plats att besöka. | Den använder en stack för att hålla reda på nästa plats att besöka. |
| BFS passerar enligt trädnivå. | DFS passerar enligt trädjupet. |
| Den implementeras med hjälp av FIFO-listan. | Den implementeras med hjälp av LIFO-listan. |
| Det kräver mer minne jämfört med DFS. | Det kräver mindre minne jämfört med BFS. |
| Denna algoritm ger den grundaste lösningen. | Denna algoritm garanterar inte den grundaste väglösningen. |
| Det finns inget behov av backtracking i BFS. | Det finns ett behov av backtracking i DFS. |
| Du kan aldrig fångas i ändliga öglor. | Du kan fångas i oändliga öglor. |
| Om du inte hittar något mål kan du behöva utöka många noder innan lösningen hittas. | Om du inte hittar något mål kan bladspårets backtracking inträffa. |
Tillämpningar av BFS
Här är applikationer av BFS:
Oviktade grafer:
BFS-algoritmen kan enkelt skapa den kortaste banan och ett minimalt spännande träd för att besöka alla hörn i grafen på kortast möjliga tid med hög noggrannhet.
P2P-nätverk:
BFS kan implementeras för att lokalisera alla närmaste eller närliggande noder i ett peer-to-peer-nätverk. Detta kommer att hitta nödvändiga data snabbare.
Webcrawlers:
Sökmotorer eller webbsökare kan enkelt bygga flera nivåer av index genom att använda BFS. BFS-implementering börjar från källan, som är webbsidan, och sedan besöker den alla länkar från den källan.
Nätverkssändning:
Ett sändningspaket styrs av BFS-algoritmen för att hitta och nå alla noder det har adressen till.
Tillämpningar av DFS
Här är viktiga tillämpningar av DFS:
Vägt diagram:
I ett viktat diagram genererar DFS-grafgenomgång det kortaste banaträdet och det minsta spännande trädet.
Upptäcka en cykel i en graf:
En graf har en cykel om vi hittade en bakre kant under DFS. Därför bör vi köra DFS för grafen och verifiera för bakre kanter.
Sökväg:
Vi kan specialisera oss i DFS-algoritmen för att söka en sökväg mellan två hörnpunkter.
Topologisk sortering:
Den används främst för att schemalägga jobb från givna beroenden bland arbetsgruppen. Inom datavetenskap används den i schemaläggning av instruktioner, dataserialisering, logisk syntes, bestämning av ordningen på sammanställningsuppgifter.
Söka efter starkt anslutna komponenter i en graf:
Det används i DFS-diagram när det finns en väg från varje toppunkt i diagrammet till andra återstående toppar.
Lösa pussel med bara en lösning:
DFS-algoritmen kan enkelt anpassas för att söka i alla lösningar till en labyrint genom att inkludera noder på den befintliga sökvägen i den besökta uppsättningen.
NYCKELSKILLNADER:
- BFS hittar den kortaste vägen till destinationen medan DFS går till botten av ett underträd och sedan spårar tillbaka.
- Den fullständiga formen av BFS är Breadth-First Search medan hela formen av DFS är Depth First Search.
- BFS använder en kö för att hålla reda på nästa plats att besöka. medan DFS använder en stack för att hålla reda på nästa plats att besöka.
- BFS passerar enligt trädnivå medan DFS passerar enligt trädjup.
- BFS implementeras med hjälp av FIFO-listan å andra sidan DFS implementeras med hjälp av LIFO-listan.
- I BFS kan du aldrig fångas i ändliga öglor medan du i DFS kan fångas i oändliga öglor.