BFS vs DFS: Vet skillnaden

Vad är BFS ?

BFS är en algoritm som används för att rita data eller söka i träd eller genomgående 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.

När du har 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-handledning för binärt träd, du lär dig:

• Vad är BFS?
• Vad är DFS?
• Exempel på BFS
• Exempel på DFS
• Skillnad mellan BFS och DFS binärt träd
• 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, vi har använt diagram med 6 hörn.

Exempel på BFS

Steg 1)

Du har en graf med sju siffror 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 data struktur som kallas stack.

Steg 2)

Du besöker elementet , som är högst upp i stapeln, till exempel 1 och går till dess intilliggande noder. Det beror på att 0 redan har besökts. Därför besöker vi topp 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 besöker vi det sista toppunktet 3, det har inga oönskade angränsande noder. Vi har slutfört grafens genomgång med DFS-algoritm.

Skillnad mellan BFS och DFS binärt träd

BFS	DFS
BFS hittar den kortaste vägen till destinationen.	DFS går till botten av ett underträd, 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ädjup.
Det implementeras med FI FO-lista.	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 väglö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 utvidga många noder innan lösningen hittas.	Om du inte hittar något mål kan bladnodens backtracking inträffa.

Tillämpningar av BFS

Här är applikationer av BFS:

Oviktad Grafer:

BFS-algoritm kan enkelt skapa den kortaste banan och ett minimalt spännande träd för att besöka alla kurvor 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.

Webbsökare:

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 applikationer för DFS:

Viktad graf:

I ett viktat diagram genererar DFS-grafgenomgång det kortaste stigträdet och det minsta spännande trädet.

Upptäcka en cykel i en graf:

En graf har en cykel om vi hittade en bakkant under DFS. Därför bör vi köra DFS för grafen och verifiera för bakre kanter.

Sökning av sökväg:

Vi kan specialisera oss i DFS-algoritmen för att söka en sökväg mellan två hörn.

Topologisk sortering:

Den används främst för att schemalägga jobb från givna beroenden bland arbetsgruppen. Inom datavetenskap används det i schemaläggning av instruktioner, dataserialisering, logisk syntes, bestämning av ordningen på sammanställningsuppgifter.

Söka efter starkt anslutna komponenter i en graf:

Den används i DFS-diagram när det finns en sökväg från varje toppunkt i diagrammet till andra återstående toppar.

Lösa pussel med endast en lösning:

DFS-algoritm 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.