COMPARACIÓN ENTRE LAS BÚSQUEDAS EN PROFUNDIDAD Y EN AMPLITUD

Las descripciones de los dos métodos de recorrido son un tanto ambiguas. Por ejemplo, si hay dos vértices adyacentes a v, ¿cuál se visitará primero? La respuesta depende de los detalles de la implementación; por ejemplo, de la forma en que se numeran o acomodan los vértices en la representación de G. Una implementación eficiente de cualquiera de los dos métodos debe mantenerse al tanto de cuáles vértices ya se visitaron pero tienen vértices adyacentes que todavía no se han visitado.

Cabe señalar que cuando una búsqueda primero en profundidad retrocede después de llegar a un callejón sin salida, supuestamente debe seguir otra rama desde el vértice visitado más recientemente antes de explorar nuevos caminos que salen de vértices visitados hace más tiempo. Por tanto, los vértices desde los que la exploración es incompleta se procesan en orden de último en entrar primero en salir (LIFO), característico de una pila. Por otra parte, en una búsqueda primero en amplitud, a fin de garantizar que los vértices cercanos a v se visiten antes que los más lejano, los vértices a explorar se organizan en una cola FIFO.

A menudo es necesario realizar algún tipo de procesamiento con cada arista. Las descripciones de los algoritmos no mencionan todas las aristas explícitamente, pero es obvio que la implementación de las líneas que requieren hallar un vértice no visitado adyacente a un vértice dado, digamos v, implicaría examinar las aristas que inciden en v, y el procesamiento necesario de las aristas podría efectuarse ahí.

La búsqueda primero en profundidad contiene dos oportunidades de procesamiento para v (cuando se visita y cuando se marca como "terminado"), mientras que la búsqueda primero en amplitud sólo contiene una (cuando se saca de la cola). En ambas búsquedas, la primera oportunidad de procesamiento se presenta mientras hay vértices no visitados a los que se puede llegar desde v.

Por otra parte, en la búsqueda en profundidad hay también una oportunidad de procesamiento en orden posterior, justo antes de que la búsqueda retroceda por fin desde v. En ese momento, en general, se han descubierto muchos más vértices y se podría haber acumulado mucha más información durante la búsqueda. El paso de procesamiento en orden posterior a menudo puede aprovechar esta información adicional para realizar cálculos mucho más complejos que los que podían realizarse en la oportunidad de orden previo. La presencia de esta oportunidad de procesamiento en orden posterior en la búsqueda primero en profundidad explica, de forma muy profunda, por qué hay tantas aplicaciones de ese tipo de búsqueda y relativamente pocas de la búsqueda primero en amplitud.