Diferența dintre BFS VS DFS
Breadth-First Search (BFS) și Depth First Search (DFS) sunt doi algoritmi importanți utilizați pentru căutare. Căutare Breadth-First își începe căutarea de la primul nod și apoi se deplasează pe nivelurile care sunt mai apropiate de nodul rădăcină în timp ce algoritmul Depth First Search începe cu primul nod și apoi își completează calea către nodul final al căii respective. Ambii algoritmi traversează fiecare nod în timpul căutării. Coduri diferite sunt scrise pentru cei doi algoritmi pentru a executa procesul de traversare. De asemenea, sunt considerați ca algoritmi importanți de căutare în inteligența artificială.
În acest subiect, vom afla despre BFS VS DFS.
Cum funcționează BFS și DFS?
Mecanismul de lucru al ambilor algoritmi este explicat mai jos cu exemple. Vă rugăm să vă consultați pentru o mai bună înțelegere a abordării utilizate.
Exemplu de căutare pentru prima lărgime
- Pasul 1: N1 este nodul rădăcină, deci va începe de aici. N1 este conectat cu trei noduri N2, N3 și N4. Toate cele trei noduri nu sunt încă vizitate. Deci, pornim de la N2 și îl depozităm în coadă. Deci, coada numită Q conține doar N2.
Î: N2
- Pasul 2: Următorul nod care este conectat la N1 este N3. De când am dat peste sau am vizitat nodul, îl vom stoca în coadă. Deci, coada actualizată este
Î: N3, N2
- Pasul 3: Următorul nod care este conectat la nodul rădăcină este N4. Îl vom depozita la coadă.
Î: N4, N3, N2
- Pasul 4: Toate nodurile care sunt conectate la N1 sunt stocate în coadă. Acum, eliminăm N2 din coadă conform principiului First in First Out (FIFO) și găsim nodurile care sunt conectate la N2 adică N5. N5 nu este vizitat o dată, așa că îl vom depozita în coadă.
Î: N5, N4, N3
- Pasul 5: Toate vârfurile sunt vizitate, așa că continuăm să eliminăm nodurile din coadă până când sunt goale.
Adâncime Primul exemplu de căutare
- Pasul 1: Vom începe cu N1 ca nod de pornire și îl vom stoca într-o stivă S. N1 este conectat cu trei noduri vecine N2, N3 și N4. Începând cu N2 (puteți începe alfabetic sau numeric), vom pune acest lucru în stivă.
S: N2 (Sus), N1
- Pasul 2: Acum, nodurile vecine ale N2 sunt N1 și N5. Deoarece N1 este deja prezent în stivă, înseamnă că este vizitat, deci vom lua N5 și îl vom pune în stiva S.
S: N5 (Sus), N2, N1
- Pasul 3: Acum, nodurile vecine ale N5 sunt N3 și N4. Începem va N3 și îl vom pune în stivă.
S: N3 (Sus), N5, N2, N1
Acum N3 este conectat la N5 și N1, care sunt deja prezente în stivă, ceea ce înseamnă că sunt vizitate, astfel încât vom elimina N3 din stivă conform principiului Last in First Out (LIFO).
S: N5 (Sus), N2, N1
- Pasul 4: Acum vom pune ultimul nod care a fost că nu am întâlnit în întreaga traversare în N4 și îl vom pune în stivă.
S: N4 (Sus), N5, N2, N1
- Pasul 5: Acum nu avem rămas cu niciun alt nod, astfel încât vom verifica în stivă dacă există noduri conectate la nodurile respective prezente în acesta care nu sunt vizitate. Dacă toate nodurile conectate sunt vizitate, atunci vom elimina nodurile prezente în stivă. De exemplu, N4 nu are noduri de conectare pe care nu le-am verificat, astfel încât îl vom elimina din stivă. În mod similar, putem verifica și alte noduri. Algoritmul se oprește odată ce stiva este goală.
Comparație față în față între BFS VS DFS (Infografie)
Mai jos sunt cele mai mari 6 diferențe între BFS VS DFS
Diferențe cheie între BFS și DFS
Să discutăm unele dintre diferențele cheie majore între BFS și DFS
- Search Breadth-First (BFS) pornește de la nodul rădăcină și vizitează toate nodurile respective atașate acestuia în timp ce DFS pornește de la nodul rădăcină și completează calea completă atașată nodului.
- BFS urmărește abordarea Coadă în timp ce DFS urmează abordarea Stack.
- Abordarea folosită în BFS este optimă, în timp ce procesul utilizat în DFS nu este optim.
- Dacă obiectivul nostru este să găsim calea cea mai scurtă decât BFS este preferată decât DFS.
Tabelul de comparare BFS și DFS
Să discutăm comparația de top dintre BFS și DFS
| BFS | DFS |
| Forma completă de BFS este Breadth-First Search. | Forma completă de DFS este Depth First Search |
| BFS este destinat să găsească cea mai scurtă distanță și pornește de la primul nod sau rădăcină și se deplasează pe toate nodurile sale atașate la nodurile respective. Puteți obține o vedere clară a mecanismului său de lucru după ce parcurgeți exemplul de mai jos. | DFS urmează o abordare bazată pe adâncime și completează calea completă prin toate nodurile atașate la nodul respectiv. Puteți obține o vedere clară a mecanismului său de lucru după ce parcurgeți exemplul de mai jos. |
| Se realizează folosind principiul Coadă, care este abordarea First In First Out (FIFO). | Se realizează folosind principiul Stack, care este abordarea Last In First out (LIFO). |
| Nodurile care sunt traversate de mai multe ori sunt eliminate din coadă. | Nodurile care sunt vizitate sunt introduse în stivă și ulterior dacă nu mai sunt noduri care trebuie vizitate, atunci acestea sunt eliminate. |
| Este relativ mai lent decât căutarea în profunzime. | Este mai rapid decât algoritmul Breadth-First Search. |
| Alocarea memoriei este mai mult decât algoritmul Primă căutare în profunzime. | Alocarea memoriei este comparativ mai mică decât algoritmul Breadth First Search |
Concluzie
Există multe aplicații în care algoritmii de mai sus sunt folosiți ca mașină de învățare sau pentru a găsi soluții legate de inteligența artificială etc. Acestea sunt utilizate în principal în grafice pentru a afla dacă este bipartit sau nu, pentru a detecta cicluri sau componente conectate. De asemenea, sunt considerați ca algoritmi importanți în găsirea căii sau pentru a găsi distanța cea mai scurtă. În funcție de cerințele afacerii, putem folosi doi algoritmi. Cu toate acestea, Breadth-First Search este considerat un mod optim, mai degrabă decât algoritmul Deepth First Search.
Articole recomandate
Acesta este un ghid pentru BFS VS DFS. Aici vom discuta despre diferențele cheie ale BFS VS DFS cu infografie și tabelul de comparație. De asemenea, puteți arunca o privire la următoarele articole pentru a afla mai multe -
- Algoritmul BFS
- TeraData vs Oracle
- Big Data vs Data Warehouse
- Big Data vs Apache Hadoop: Top 4 comparație pe care trebuie să o înveți