Abans de veure les diferències entre BFS i DFS, primer hauríem de conèixer BFS i DFS per separat.
Què és BFS?
BFS significa Primera recerca d'amplada . També es coneix com recorregut d'ordre de nivell . L'estructura de dades de la cua s'utilitza per al recorregut de Breadth First Search. Quan utilitzem l'algorisme BFS per al recorregut en un gràfic, podem considerar qualsevol node com a node arrel.
Considerem el gràfic següent per a l'amplitud de la primera cerca.
llegir des del fitxer csv en java
Suposem que considerem el node 0 com un node arrel. Per tant, el recorregut s'iniciaria des del node 0.
Un cop eliminat el node 0 de la cua, s'imprimeix i es marca com a node visitat.
Un cop eliminat el node 0 de la cua, els nodes adjacents del node 0 s'inseririen en una cua tal com es mostra a continuació:
Ara el node 1 s'eliminarà de la cua; s'imprimeix i es marca com a node visitat
Una vegada que el node 1 s'elimina de la cua, tots els nodes adjacents d'un node 1 s'afegiran a una cua. Els nodes adjacents del node 1 són 0, 3, 2, 6 i 5. Però hem d'inserir només nodes no visitats en una cua. Com que els nodes 3, 2, 6 i 5 no són visitats; per tant, aquests nodes s'afegiran en una cua tal com es mostra a continuació:
El següent node és 3 en una cua. Per tant, el node 3 s'eliminarà de la cua, s'imprimirà i es marcarà com a visitat tal com es mostra a continuació:
Un cop eliminat el node 3 de la cua, s'afegiran a una cua tots els nodes adjacents del node 3, excepte els nodes visitats. Els nodes adjacents del node 3 són 0, 1, 2 i 4. Com que els nodes 0, 1 ja estan visitats i el node 2 està present en una cua; per tant, hem d'inserir només el node 4 en una cua.
identificadors vàlids a Java
Ara, el següent node de la cua és 2. Per tant, 2 s'eliminaria de la cua. S'imprimeix i es marca com a visitat tal com es mostra a continuació:
Un cop eliminat el node 2 de la cua, s'afegiran a una cua tots els nodes adjacents del node 2, excepte els nodes visitats. Els nodes adjacents del node 2 són 1, 3, 5, 6 i 4. Com que els nodes 1 i 3 ja s'han visitat, i 4, 5, 6 ja s'han afegit a la cua; per tant, no necessitem inserir cap node a la cua.
El següent element és 5. Per tant, 5 s'eliminaria de la cua. S'imprimeix i es marca com a visitat tal com es mostra a continuació:
Un cop eliminat el node 5 de la cua, s'afegiran a la cua tots els nodes adjacents del node 5 excepte els nodes visitats. Els nodes adjacents del node 5 són 1 i 2. Com que ambdós nodes ja han estat visitats; per tant, no hi ha cap vèrtex per inserir en una cua.
El següent node és 6. Per tant, 6 s'eliminaria de la cua. S'imprimeix i es marca com a visitat tal com es mostra a continuació:
Un cop eliminat el node 6 de la cua, s'afegiran a la cua tots els nodes adjacents del node 6 excepte els nodes visitats. Els nodes adjacents del node 6 són l'1 i el 4. Com que el node 1 ja s'ha visitat i el node 4 ja s'ha afegit a la cua; per tant, no hi ha vèrtex per inserir a la cua.
El següent element de la cua és 4. Per tant, 4 s'eliminaria de la cua. S'imprimeix i es marca com a visitat.
Un cop eliminat el node 4 de la cua, tots els nodes adjacents del node 4 excepte els nodes visitats s'afegiran a la cua. Els nodes adjacents del node 4 són 3, 2 i 6. Com que tots els nodes adjacents ja han estat visitats; per tant, no hi ha cap vèrtex per inserir a la cua.
Què és DFS?
DFS significa Depth First Search. En el recorregut DFS, s'utilitza l'estructura de dades de pila, que funciona segons el principi LIFO (Last In First Out). A DFS, el recorregut es pot iniciar des de qualsevol node, o podem dir que qualsevol node es pot considerar com un node arrel fins que el node arrel no s'esmenta al problema.
En el cas de BFS, l'element que s'elimina de la cua, els nodes adjacents del node suprimit s'afegeixen a la cua. En canvi, a DFS, l'element que s'elimina de la pila, només s'afegeix un node adjacent d'un node suprimit a la pila.
Considerem el gràfic següent per al recorregut de la primera cerca de profunditat.
java analitza la cadena a int
Considereu el node 0 com a node arrel.
python rstrip
Primer, inserim l'element 0 a la pila tal com es mostra a continuació:
El node 0 té dos nodes adjacents, és a dir, 1 i 3. Ara només podem agafar un node adjacent, ja sigui 1 o 3, per recórrer. Suposem que considerem el node 1; per tant, s'insereix 1 en una pila i s'imprimeix com es mostra a continuació:
Ara veurem els vèrtexs adjacents del node 1. Els vèrtexs adjacents no visitats del node 1 són 3, 2, 5 i 6. Podem considerar qualsevol d'aquests quatre vèrtexs. Suposem que agafem el node 3 i l'inserim a la pila tal com es mostra a continuació:
Considereu els vèrtexs adjacents no visitats del node 3. Els vèrtexs adjacents no visitats del node 3 són 2 i 4. Podem prendre qualsevol dels vèrtexs, és a dir, 2 o 4. Suposem que agafem el vèrtex 2 i l'inserim a la pila tal com es mostra a continuació:
Els vèrtexs adjacents no visitats del node 2 són 5 i 4. Podem triar qualsevol dels vèrtexs, és a dir, 5 o 4. Suposem que agafem el vèrtex 4 i l'inserim a la pila tal com es mostra a continuació:
Ara considerarem els vèrtexs adjacents no visitats del node 4. El vèrtex adjacent no visitat del node 4 és el node 6. Per tant, l'element 6 s'insereix a la pila tal com es mostra a continuació:
Després d'inserir l'element 6 a la pila, mirarem els vèrtexs adjacents no visitats del node 6. Com que no hi ha vèrtexs adjacents no visitats del node 6, no podem moure més enllà del node 6. En aquest cas, realitzarem retrocés . L'element superior, és a dir, 6 sortiria de la pila tal com es mostra a continuació:
L'element superior de la pila és 4. Com que no queden vèrtexs adjacents no visitats del node 4; per tant, el node 4 surt de la pila tal com es mostra a continuació:
El següent element superior de la pila és 2. Ara, veurem els vèrtexs adjacents no visitats del node 2. Com que només queda un node no visitat, és a dir, 5, per tant, el node 5 s'empeny a la pila per sobre de 2 i s'imprimeix. com es mostra a continuació:
Ara comprovarem els vèrtexs adjacents del node 5, que encara no són visitats. Com que no queda cap vèrtex per visitar, de manera que extreu l'element 5 de la pila tal com es mostra a continuació:
No podem avançar més 5, així que hem de fer marxa enrere. En retrocedir, l'element superior sortiria de la pila. L'element superior és 5 que sortiria de la pila i tornem al node 2 tal com es mostra a continuació:
tipus de dades seqüeles
Ara comprovarem els vèrtexs adjacents no visitats del node 2. Com que no queda cap vèrtex adjacent per visitar, fem una marxa enrere. En retrocés, l'element superior, és a dir, 2 sortiria de la pila i tornem al node 3 tal com es mostra a continuació:
Ara comprovarem els vèrtexs adjacents no visitats del node 3. Com que no queda cap vèrtex adjacent per visitar, fem una marxa enrere. En retrocés, l'element superior, és a dir, 3 sortiria de la pila i tornarem al node 1 tal com es mostra a continuació:
Després de sortir l'element 3, comprovarem els vèrtexs adjacents no visitats del node 1. Com que no queda cap vèrtex per visitar; per tant, es realitzarà el retrocés. En retrocés, l'element superior, és a dir, 1, sortiria de la pila i tornem al node 0 tal com es mostra a continuació:
Comprovarem els vèrtexs adjacents del node 0, que encara no són visitats. Com que no queda cap vèrtex adjacent per ser visitat, fem una marxa enrere. En això, només un element, és a dir, 0 que queda a la pila, sortiria de la pila tal com es mostra a continuació:
Com podem observar a la figura anterior que la pila està buida. Per tant, hem d'aturar el recorregut DFS aquí, i els elements que s'imprimeixen són el resultat del recorregut DFS.
Diferències entre BFS i DFS
A continuació es mostren les diferències entre el BFS i el DFS:
| BFS | DFS | |
|---|---|---|
| Forma completa | BFS significa Breadth First Search. | DFS són les sigles de Depth First Search. |
| Tècnica | És una tècnica basada en vèrtexs per trobar el camí més curt en un gràfic. | És una tècnica basada en arestes perquè els vèrtexs al llarg de la vora s'exploren primer des del node inicial fins al final. |
| Definició | BFS és una tècnica de recorregut en què primer s'exploren tots els nodes del mateix nivell i després passem al següent nivell. | DFS també és una tècnica de recorregut en què el recorregut s'inicia des del node arrel i explora els nodes tant com sigui possible fins a arribar al node que no té nodes adjacents no visitats. |
| Estructura de dades | L'estructura de dades de la cua s'utilitza per al recorregut BFS. | L'estructura de dades de pila s'utilitza per al recorregut BFS. |
| Fes marxa enrere | BFS no utilitza el concepte de retrocés. | DFS utilitza la marxa enrere per recórrer tots els nodes no visitats. |
| Nombre d'arestes | BFS troba el camí més curt amb un nombre mínim d'arestes per recórrer des de l'origen fins al vèrtex de destinació. | A DFS, es requereix un nombre més gran d'arestes per travessar des del vèrtex d'origen fins al vèrtex de destinació. |
| Optimitat | El recorregut BFS és òptim per a aquells vèrtexs que s'han de cercar més a prop del vèrtex font. | El recorregut DFS és òptim per a aquells gràfics en què les solucions estan lluny del vèrtex font. |
| Velocitat | BFS és més lent que DFS. | DFS és més ràpid que BFS. |
| Idoneïtat per a l'arbre de decisió | No és adequat per a l'arbre de decisió perquè requereix explorar primer tots els nodes veïns. | És adequat per a l'arbre de decisió. A partir de la decisió, explora tots els camins. Quan es troba l'objectiu, atura el seu recorregut. |
| Memòria eficient | No és eficient amb la memòria, ja que requereix més memòria que DFS. | És eficient en memòria, ja que requereix menys memòria que BFS. |