Algoritmo recursivo de búsqueda primero en profundidad.

operación bpp (v: nodo)

                marca[v]:= visitado

                para cada nodo w adyacente a v hacer

                     si marca[w] == noVisitado entonces

                                               bpp(w)

                finpara

Método en donde se hace el llamado al algoritmo bpp()

operación BúsquedaPrimeroEnProfundidad

                BorraMarcas

                para v:= 1, ..., n hacer

                                si marca[v] == noVisitado entonces

                                               bpp(v)

                finpara

 

El recorrido no es único: depende del nodo inicial y del orden de visita de los adyacentes.

El orden de visita de unos nodos a partir de otros puede ser visto como un árbol: árbol de expansión en profundidad asociado al grafo.

Si aparecen varios árboles: bosque de expansión en profundidad.

Ejemplo 1 Grafo no dirigido.

Árbol de expansión en profundidad:

Arcos no del árbol: si marca[v] == noVisitado ...

→ se detectan cuando la condición es falsa.

Ejemplo 2 Grafo dirigido.                                               Árbol de expansión en profundidad:

 

•          ¿Cuánto es el tiempo de ejecución de  BPP?

•          Imposible predecir las llamadas en cada ejecución.

•          Solución: medir el “trabajo total realizado”.