Înainte de a analiza diferențele dintre BFS și DFS, mai întâi ar trebui să știm despre BFS și DFS separat.

Ce este BFS?

BFS reprezintă Latimea prima cautare . Este cunoscut și ca traversarea ordinii de nivel . Structura de date Queue este utilizată pentru traversarea Breadth First Search. Când folosim algoritmul BFS pentru traversarea într-un grafic, putem considera orice nod ca un nod rădăcină.

Să luăm în considerare graficul de mai jos pentru prima traversare a căutării.

dimensiunile fonturilor în latex

Să presupunem că considerăm nodul 0 ca un nod rădăcină. Prin urmare, traversarea ar fi începută de la nodul 0.

Odată ce nodul 0 este eliminat din coadă, acesta este tipărit și marcat ca a nodul vizitat.

Odată ce nodul 0 este eliminat din coadă, atunci nodurile adiacente ale nodului 0 vor fi inserate într-o coadă, după cum se arată mai jos:

Acum nodul 1 va fi eliminat din coadă; este tipărit și marcat ca nod vizitat

Odată ce nodul 1 este eliminat din coadă, atunci toate nodurile adiacente ale unui nod 1 vor fi adăugate într-o coadă. Nodurile adiacente ale nodului 1 sunt 0, 3, 2, 6 și 5. Dar trebuie să inserăm doar noduri nevizitate într-o coadă. Deoarece nodurile 3, 2, 6 și 5 nu sunt vizitate; prin urmare, aceste noduri vor fi adăugate într-o coadă, după cum se arată mai jos:

Următorul nod este 3 într-o coadă. Deci, nodul 3 va fi eliminat din coadă, este tipărit și marcat ca vizitat, după cum se arată mai jos:

Odată ce nodul 3 este eliminat din coadă, atunci toate nodurile adiacente ale nodului 3, cu excepția nodurilor vizitate, vor fi adăugate într-o coadă. Nodurile adiacente ale nodului 3 sunt 0, 1, 2 și 4. Deoarece nodurile 0, 1 sunt deja vizitate, iar nodul 2 este prezent într-o coadă; prin urmare, trebuie să inserăm doar nodul 4 într-o coadă.

.next java

Acum, următorul nod din coadă este 2. Deci, 2 ar fi șters din coadă. Acesta este tipărit și marcat ca vizitat, după cum se arată mai jos:

Odată ce nodul 2 este eliminat din coadă, atunci toate nodurile adiacente ale nodului 2, cu excepția nodurilor vizitate, vor fi adăugate într-o coadă. Nodurile adiacente ale nodului 2 sunt 1, 3, 5, 6 și 4. Deoarece nodurile 1 și 3 au fost deja vizitate și 4, 5, 6 sunt deja adăugate în coadă; prin urmare, nu trebuie să inserăm niciun nod în coadă.

Următorul element este 5. Deci, 5 ar fi șters din coadă. Acesta este tipărit și marcat ca vizitat, după cum se arată mai jos:

Odată ce nodul 5 este eliminat din coadă, atunci toate nodurile adiacente ale nodului 5, cu excepția nodurilor vizitate, vor fi adăugate în coadă. Nodurile adiacente ale nodului 5 sunt 1 și 2. Deoarece ambele noduri au fost deja vizitate; prin urmare, nu există un vârf de inserat într-o coadă.

Următorul nod este 6. Deci, 6 ar fi șters din coadă. Acesta este tipărit și marcat ca vizitat, după cum se arată mai jos:

Odată ce nodul 6 este eliminat din coadă, atunci toate nodurile adiacente ale nodului 6, cu excepția nodurilor vizitate, vor fi adăugate în coadă. Nodurile adiacente ale nodului 6 sunt 1 și 4. Deoarece nodul 1 a fost deja vizitat și nodul 4 este deja adăugat în coadă; prin urmare, nu există un vârf de inserat în coadă.

Următorul element din coadă este 4. Deci, 4 ar fi șters din coadă. Este tipărit și marcat ca vizitat.

Odată ce nodul 4 este eliminat din coadă, atunci toate nodurile adiacente ale nodului 4, cu excepția nodurilor vizitate, vor fi adăugate în coadă. Nodurile adiacente ale nodului 4 sunt 3, 2 și 6. Deoarece toate nodurile adiacente au fost deja vizitate; deci, nu există un vârf de inserat în coadă.

Ce este DFS?

DFS reprezintă Depth First Search. În traversarea DFS, este utilizată structura de date a stivei, care funcționează pe principiul LIFO (Last In First Out). În DFS, traversarea poate fi începută de la orice nod, sau putem spune că orice nod poate fi considerat ca un nod rădăcină până când nodul rădăcină nu este menționat în problemă.

În cazul BFS, elementul care este șters din coadă, nodurile adiacente ale nodului șters sunt adăugate la coadă. În contrast, în DFS, elementul care este eliminat din stivă, apoi numai un nod adiacent al unui nod șters este adăugat în stivă.

diferența dintre un tigru și un leu

Să luăm în considerare graficul de mai jos pentru traversarea Depth First Search.

Considerați nodul 0 ca nod rădăcină.

Mai întâi, inserăm elementul 0 în stivă, așa cum se arată mai jos:

Nodul 0 are două noduri adiacente, adică 1 și 3. Acum putem lua doar un nod adiacent, fie 1, fie 3, pentru parcurgere. Să presupunem că luăm în considerare nodul 1; prin urmare, 1 este introdus într-un teanc și este tipărit așa cum se arată mai jos:

Acum ne vom uita la vârfurile adiacente ale nodului 1. Nodurile adiacente nevizitate ale nodului 1 sunt 3, 2, 5 și 6. Putem lua în considerare oricare dintre aceste patru vârfuri. Să presupunem că luăm nodul 3 și îl introducem în stivă, așa cum se arată mai jos:

Luați în considerare vârfurile adiacente nevizitate ale nodului 3. Vârfurile adiacente nevizitate ale nodului 3 sunt 2 și 4. Putem lua oricare dintre vârfuri, adică 2 sau 4. Să presupunem că luăm vârful 2 și îl inserăm în stiva, așa cum se arată mai jos:

Vârfurile adiacente nevizitate ale nodului 2 sunt 5 și 4. Putem alege oricare dintre vârfuri, adică 5 sau 4. Să presupunem că luăm vârful 4 și inserăm în stivă așa cum se arată mai jos:

jvm în java

Acum vom lua în considerare vârfurile adiacente nevizitate ale nodului 4. Vârful adiacent nevizitat al nodului 4 este nodul 6. Prin urmare, elementul 6 este inserat în stiva după cum se arată mai jos:

După inserarea elementului 6 în stivă, ne vom uita la vârfurile adiacente nevizitate ale nodului 6. Deoarece nu există vârfuri adiacente nevizitate ale nodului 6, nu ne putem deplasa dincolo de nodul 6. În acest caz, vom efectua dare înapoi . Elementul cel mai de sus, adică 6, va fi scos din stivă, așa cum se arată mai jos:

Elementul cel mai de sus din stiva este 4. Deoarece nu există vârfuri adiacente nevizitate rămase ale nodului 4; prin urmare, nodul 4 este scos din stivă, așa cum se arată mai jos:

Următorul element cel mai de sus din stivă este 2. Acum, ne vom uita la vârfurile adiacente nevizitate ale nodului 2. Deoarece a rămas un singur nod nevizitat, adică 5, deci nodul 5 va fi împins în stiva de deasupra lui 2 și va fi imprimat așa cum se arată mai jos:

Acum vom verifica vârfurile adiacente ale nodului 5, care sunt încă nevizitate. Deoarece nu mai există un vârf de vizitat, deci scoatem elementul 5 din stivă, așa cum se arată mai jos:

diferența dintre cină și cină

Nu ne putem deplasa mai departe 5, așa că trebuie să facem backtracking. În întoarcere, elementul cel mai de sus ar fi scos din stivă. Elementul cel mai de sus este 5 care ar fi ieșit din stivă și ne întoarcem la nodul 2, așa cum se arată mai jos:

Acum vom verifica vârfurile adiacente nevizitate ale nodului 2. Deoarece nu mai există un vârf adiacent de vizitat, efectuăm backtracking. În backtracking, elementul cel mai de sus, adică 2, va fi scos din stivă și ne întoarcem la nodul 3, așa cum se arată mai jos:

Acum vom verifica vârfurile adiacente nevizitate ale nodului 3. Deoarece nu mai există un vârf adiacent de vizitat, efectuăm backtracking. În backtracking, elementul cel mai de sus, adică 3, ar fi ieșit din stivă și ne întoarcem la nodul 1, așa cum se arată mai jos:

După ce apare elementul 3, vom verifica vârfurile adiacente nevizitate ale nodului 1. Deoarece nu mai există niciun vârf de vizitat; prin urmare, se va efectua backtracking. În backtracking, elementul cel mai de sus, adică 1, ar fi ieșit din stivă și ne întoarcem la nodul 0 așa cum se arată mai jos:

Vom verifica vârfurile adiacente ale nodului 0, care sunt încă nevizitate. Deoarece nu mai există un vârf adiacent de vizitat, efectuăm backtracking. În aceasta, un singur element, adică 0 rămas în stivă, va fi scos din stivă, după cum se arată mai jos:

După cum putem observa în figura de mai sus, stiva este goală. Deci, trebuie să oprim traversarea DFS aici, iar elementele care sunt imprimate sunt rezultatul traversării DFS.

Diferențele dintre BFS și DFS

Următoarele sunt diferențele dintre BFS și DFS: