BFS vs DFS – Skillnaden mellan dem

Nyckelskillnad mellan BFS och DFS

  • BFS hittar den kortaste vägen till destinationen, medan DFS går till botten av ett underträd och backar sedan.
  • Den fullständiga formen av BFS är Breadth-First Search, medan den fullständiga 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 korsar enligt trädnivå, medan DFS korsar enligt träddjup.
  • BFS implementeras med hjälp av en FIFO-lista; å andra sidan implementeras DFS med hjälp av en LIFO-lista.
  • I BFS kan du aldrig fångas in i ändliga loopar, medan du i DFS kan fångas i oändliga loopar.
Skillnaden mellan BFS och DFS
Skillnaden mellan BFS och DFS

Vad är BFS?

BFS är en algoritm som används för att plotta data eller söka i träd eller korsa strukturer. Algoritmen besöker och markerar effektivt alla nyckelnoder i en graf på ett exakt breddmässigt sätt.

Denna algoritm väljer en enda nod (initial- eller källpunkt) i en graf och besöker sedan alla noder intill den valda noden. När algoritmen besöker och markerar startnoden, flyttar den sig mot de närmaste obesökta noderna och analyserar dem.

När de har besökts är alla noder markerade. Dessa iterationer fortsätter tills alla noder i grafen har besökts och markerats. Den fullständiga formen av BFS är Breadth-first-sökningen.

Vad är DFS?

DFS är en algoritm för att hitta eller korsa grafer eller träd i riktning mot djupet. Exekveringen av algoritmen börjar vid rotnoden och utforskar varje gren innan den går tillbaka. Den använder en stackdatastruktur för att komma ihåg, för att få den efterföljande vertexen och för att starta en sökning, närhelst en återvändsgränd dyker upp i någon iteration. Den fullständiga formen av DFS är djup-först-sökning.

Skillnaden mellan BFS och DFS Binary Tree

Här är de viktiga skillnaderna mellan BFS och DFS.

BFS DFS
BFS hittar den kortaste vägen till destinationen. DFS går till botten av ett underträd och backar sedan.
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 korsar enligt trädnivå. DFS korsar efter träddjup.
Det implementeras med hjälp av FIFO-listan. Det 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 in i ändliga loopar. Du kan fångas i oändliga loopar.
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 bladnodens backspårning inträffa.

Exempel på BFS

I följande exempel på BFS har vi använt en graf med 6 hörn.

Exempel på BFS

Steg 1)

Exempel på BFS

Du har en graf med sju tal som sträcker sig från 0 – 6.

Steg 2)

Exempel på BFS

0 eller noll har markerats som en rotnod.

Steg 3)

Exempel på BFS

0 besöks, markeras och infogas i ködatastrukturen.

Steg 4)

Exempel på BFS

Återstående 0 närliggande och obesökta noder besöks, markeras och infogas i kön.

Steg 5)

Exempel på BFS

Traverserande iterationer upprepas tills alla noder har besökts.

Exempel på DFS

I följande exempel på DFS har vi använt en oriktad graf med 5 hörn.

Exempel på DFS

Steg 1)

Exempel på DFS

Vi har börjat från vertex 0. Algoritmen börjar med att sätta den i besökslistan och samtidigt sätta alla dess närliggande hörn i datastruktur kallas stack.

Steg 2)

Exempel på DFS

Du kommer att besöka elementet, som är högst upp i stapeln, till exempel 1 och gå till dess närliggande noder. Det beror på att 0 redan har besökts. Därför besöker vi vertex 2.

Steg 3)

Exempel på DFS

Vertex 2 har ett obesökt närliggande vertex i 4. Därför lägger vi till det i stacken och besöker det.

Steg 4)

Exempel på DFS

Slutligen kommer vi att besöka den sista vertex 3, den har inga obesökta angränsande noder. Vi har slutfört genomgången av grafen med DFS-algoritm.

Exempel på DFS

Tillämpningar av BFS

Här är applikationer för BFS:

Oviktade grafer

BFS-algoritmen kan enkelt skapa den kortaste vägen och ett minimalt spännträ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 angränsande noder i ett peer-to-peer-nätverk. Detta kommer att hitta den nödvändiga informationen snabbare.

Webbsökare

Sökmotorer eller sökrobotar kan enkelt bygga flera nivåer av index genom att använda BFS. BFS-implementering startar från källan, som är webbsidan, och sedan besöker den alla länkar från den källan.

Nätverkssändning

Ett utsänt paket styrs av BFS-algoritmen för att hitta och nå alla noder som det har adressen till.

Tillämpningar av DFS

Här är viktiga tillämpningar av DFS:

Viktad graf

I en viktad graf genererar DFS-graftraversering det kortaste vägträdet och minsta spännträ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 bakkanter.

Sökväg

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

Topologisk sortering

Det används i första hand för att schemalägga jobb från de givna beroenden i gruppen av jobb. Inom datavetenskap används det i instruktionsschemaläggning, dataserialisering, logiksyntes, bestämning av ordningen för kompileringsuppgifter.

Söka efter starkt anslutna komponenter i en graf

Det används i DFS-graf när det finns en väg från varje hörn i grafen till andra återstående hörn.

Lösa pussel med bara en lösning

DFS-algoritmen kan enkelt anpassas för att söka alla lösningar till en labyrint genom att inkludera noder på den befintliga sökvägen i den besökta uppsättningen.