Cerca en profunditat

De Viquipèdia
Dreceres ràpides: navegació, cerca

Una cerca en profunditat (en anglès Depth First Search, DFS) és un algorisme que permet recórrer tots els nodes d'un arbre o graf de manera ordenada, però no uniforme. El seu funcionament es basa a anar expandint cada node que troba, de manera recursiva, recorrent tots els nodes d'un camí concret. Quan ja no queden més nodes per visitar d'aquest camí, es realitza un pas enrere (backtracking), que permet que pugui tornar a començar el mateix procés amb cadascun dels germans d'un node ja processat.

Un exemple d'arbre és:

Arbre n-ari


El resultat d'aplicar l'algorisme de cerca en profunditat sobre ell, començant per F, seria el recorregut següent: F, B, A, D, C, E, G, I,H.

De la mateixa manera, existeix l'algorisme de Cerca en Amplada (BFS - Breath First Search).

El pseudocodi d'aquest algorisme és:

DFS(G)
For each vertice u ∈ V[G]do
color[u]=WHITE
pred[u]=NIL
time=0
for each vertice u ∈ V[G]do
if color[u]=WHITE then
DFS-Visit(u)

DFS-Visit(u)
color[u]=GRAY
d[u]=time=time+1
for each v ∈ Adj[u] do
if color[v]=WHITE then
pred[v]=u
DFS-Visit(v)
color[u]=BLACK
f[u]=time=time+1


A Wikimedia Commons hi ha contingut multimèdia relatiu a: Cerca en profunditat Modifica l'enllaç a Wikidata