Unacerca en profunditat (en anglèsDepth First Search,DFS) és unalgorisme que permet recórrer tots els nodes d'un arbre ograf de manera ordenada, però no uniforme. El seu funcionament es basa a anar expandint cadanode 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.
De la mateixa manera, existeix l'algorisme decerca en amplada (BFS - breadth first search).
El segle xix, el matemàtic francèsCharles Pierre Trémaux investigà una versió de l'algorisme de cerca en profunditat com a estratègia per a laresolució de laberints.[1][2]
L'anàlisi deltemps i l'espai necessaris per a l'algorisme DFS difereix en funció de l'àrea d'aplicació. Eninformàtica teòrica, l'algorisme DFS s'utilitza per recórrer un graf sencer, i necessita un temps Θ(|V| + |E|),[3] lineal en la grandària del graf. En aquestes aplicacions, també necessita espai O(|V|) en el cas pitjor per emmagatzemar la pila de vèrtexs del camí de cerca en curs, així com el conjunt de vèrtexs ja visitats. Per tant, les fites de temps i espai són les mateixes que per l'algorisme decerca en amplada, i l'elecció de quin d'aquests dos algorismes cal utilitzar no depèn tant de la seva complexitat com de les diferents propietats de les ordenacions de vèrtexs que produeixen.
Quant a les aplicacions de l'algorisme DFS en àrees específiques, com la cerca de solucions enintel·ligència artificial o el recorregut de pàgines web per part d'aranyes web, el graf que cal recórrer és o bé molt gran o bé infinit (DFS pot patirparades). En aquests casos, una solució pot ser limitar la cerca només fins a una certaprofunditat; a causa de la limitació de recursos, com la memòria o l'espai en disc, no s'acostumen a utilitzar estructures de dades per guardar l'historial de quins vèrtexs s'han visitat. Quan es realitza la cerca fins a una profunditat limitada, el temps encara és lineal en termes del nombre de vèrtexs expandits i arestes (encara que aquest nombre no és el mateix que la grandària de tot el graf, ja que pot ser que alguns vèrtexs es recorrin més d'un cop i d'altres no es visitin), però la complexitat en espai d'aquesta variant de DFS només és proporcional a la profunditat límit, i com a resultat, molt menor que l'espai necessari per explorar fins a la mateixa profunditat mitjançant la cerca en amplada. Per a aquestes aplicacions, DFS resulta millor en la implementació de mètodesheurístics per escollir una branca apropiada. Quan no es coneixa priori una profunditat límit adequada, lacerca en profunditat iterativa aplica l'algorisme DFS repetidament amb una successió de límits creixent per a la profunditat. En el mode d'anàlisi de la intel·ligència artificial, amb unfactor de ramificació superior a 1, la cerca en profunditat iterativa incrementa el temps de procés només en un factor constant sobre el cas en què es conegui prèviament la profunditat correcta, a causa del creixement geomètric del nombre de nodes per nivell.
L'algorisme de cerca en profunditat també es pot fer servir per recollir unamostra dels nodes del graf. Tanmateix, l'algorisme DFS incomplet, de manera semblant a BFS incomplet, ésesbiaixat cap als nodes degrau elevat.
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.
Per al graf següent:
una cerca en profunditat que comenci en A, suposant que les arestes esquerres es recorren abans que les dretes, i suposant que la cerca recorda els vèrtexs visitats i no els repeteix (posat que aquest és un graf petit), recorre els nodes en aquest ordre: A, B, D, F, E, C, G. Les arestes recorregudes formen unarbre de Trémaux, una estructura amb aplicacions importants enteoria de grafs.
Si es realitza la mateixa cerca sense recordar els vèrtexs prèviament visitats, l'ordre seria A, B, D, F, E, A, B, D, F, E, etc. infinitament, atrapada en el cicle A, B, D, F, E i mai no arribaria a C o G.
Lacerca en profunditat iterativa és una tècnica per evitar aquest bucle infinit i s'arribaria a tots els nodes.
Una descripció convenient d'una cerca en profunditat d'un graf és en termes d'unarbre d'expansió dels vèrtexs visitats durant la cerca. Basant-se en aquest arbre d'expansió, es poden classificar les arestes del graf original en tres tipus:arestes cap endavant, que apunten d'un node de l'arbre cap a un dels seus descendents,arestes cap enrere, que apunten d'un node a un dels seus superiors, iarestes creuades, que són aquelles que no pertanyen a cap dels dos tipus anteriors. De vegades, hom afegeix un quart tipus separat de les arestes cap endavant, lesarestes de l'arbre, que són les arestes que pertanyen a l'arbre d'expansió. Si el graf original és no dirigit, llavors totes les seves arestes són arestes de l'arbre o arestes cap enrere.
També és possible emprar la cerca en profunditat per ordenar linealment els vèrtexs del graf (o arbre) original. Hi ha tres maneres habituals de fer-ho:
si (A) llavors {B} sinó {C}DEntrada: Un grafG i un vèrtexv deG.
Sortida: Tots els vèrtexs que es poden visitar des dev, marcats com a visitats.
Una implementació recursiva de DFS:[4][5]
1procediment DFS(G,v):2 etiquetarv com a visitat3per a tota aresta dev cap awenG.arestesAdjacents(v)fer4si el vèrtexw no està etiquetat com a visitatllavors5 cridar recursivament DFS(G,w)
Una implementació no recursiva de DFS:[6]
1procediment DFS-iteratiu(G,v):2 siguiS una pila3S.empila(v)4mentreS no és buida5v =S.desempila()6siv no està etiquetat com a visitat:7 etiquetarv com a visitat8per a tota aresta dev cap awenG.arestesAdjacents(v)fer9S.empila(w)
Aquestes dues variants de l'algorisme DFS visiten els veïns de cada vèrtex en ordre invers l'una de l'altra: el primer veí dev que visita la variant recursiva és el primer en la llista d'arestes adjacents, mentre que en la variant iterativa el primer vèrtex visitat és l'últim de la llista d'arestes adjacents. La implementació recursiva visita els nods del graf d'exemple en l'ordre A, B, D, F, E, C, G. La implementació iterativa visita els nodes en l'ordre A, E, F, B, D, C, G. La variant iterativa és semblant a lacerca en amplada, però difereixen en dos aspectes: utilitza unapila en comptes d'unacua, i no es comprova si un vèrtex s'ha visitat fins que aquest vèrtex s'ha desempilat, en comptes de verificar-ho abans d'empilar-lo. Notem que aquesta implementació iterativa de DFS pot arribar a utilitzar un espaiO(|E|) en el cas pitjor, per exemple en ungraf complet.
Alguns problemes que admeten solucions mitjançant l'aplicació de la cerca en profunditat són:
Lacomplexitat computacional de l'algorisme DFS fou investigada per Reif, que va demostrar que unaversió de decisió (determinar si un vèrtexu apareix abans d'un vèrtexv en una ordenació DFS d'un graf amb arrel) ésP-complet,[9] la qual cosa significava que és "un malson per alprocessament paral·lel".[10]
La complexitat en temps és per a grafs explícits recorreguts sense repetició, i per a grafs implícits amb un factor de ramificaciób explorats fins a la profunditatd. La complexitat en espai és si s'explora el graf sencer sense repetició, iO(longitud del camí més llarg recorregut) per a grafs implícits sense eliminació dels nodes duplicats.
