Cerca en profunditat
De Viquipèdia
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 en 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:
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
