¿Por qué se afirma que la búsqueda en profundidad es eficiente desde el punto de vista del espacio?

En un curso de algoritmos que estoy tomando, se dice que la búsqueda en profundidad (DFS) es mucho más eficiente en el uso del espacio que la búsqueda de amplitud (BFS).

¿Porqué es eso?

Aunque básicamente están haciendo lo mismo, en DFS estamos astackndo los sucesores actuales mientras que en BFS estamos enquistando a los sucesores.

    Su confusión se deriva del hecho de que aparentemente asume que el algoritmo DFS puede obtenerse del algoritmo BFS al reemplazar la cola FIFO con una stack LIFO.

    Este es un concepto erróneo popular, simplemente no es verdad. El clásico algoritmo DFS no se puede obtener reemplazando la cola BFS con una stack. La diferencia entre estos algoritmos es mucho más significativa.

    Si toma un algoritmo BFS y simplemente reemplaza la cola FIFO con una stack LIFO, obtendrá algo que se puede llamar un algoritmo pseudo-DFS . Este algoritmo pseudo-DFS reproducirá correctamente la secuencia de cruce directo del vértice DFS, pero no tendrá la eficacia del espacio DFS y no admitirá el recorrido hacia atrás del DFS (retroceso).

    Mientras tanto, el verdadero DFS clásico no se puede obtener de BFS mediante un reemplazo ingenuo de la cola a la stack. El DFS clásico es un algoritmo completamente diferente con una estructura central significativamente diferente. True DFS es un algoritmo genuinamente recursivo que utiliza la stack para fines de seguimiento , no para almacenar el descubrimiento de vértices “frontal” (como es el caso en BFS). La consecuencia más inmediata de eso es que en el algoritmo DFS, la profundidad máxima de la stack es igual a la distancia máxima desde el vértice de origen en el cruce DFS. En el algoritmo BFS (como en el pseudo-DFS antes mencionado), el tamaño máximo de cola es igual al ancho del frente de descubrimiento de vértices más grande.

    El ejemplo más destacado y extremo que ilustra la diferencia en el consumo máximo de memoria entre DFS y BFS (así como pseudo-DFS) es un gráfico de estrellas: un solo vértice central rodeado de un gran número (digamos, 1000 ) de vértices periféricos, con cada vértice periférico conectado al vértice central por un borde. Si ejecuta BFS en este gráfico utilizando el vértice central como origen, el tamaño de la cola saltará inmediatamente a 1000 . Lo mismo sucederá obviamente si usa pseudo-DFS (es decir, si simplemente reemplaza la cola con una stack). Pero el algoritmo DFS clásico necesitará una profundidad de stack de solo 1 (!) Para recorrer todo este gráfico. ¿Ver la diferencia? 1000 contra 1 . Esto es lo que se entiende por una mejor eficiencia del espacio de DFS.

    Básicamente, tome cualquier libro sobre algoritmos, encuentre una descripción del DFS clásico y vea cómo funciona. Notarás que la diferencia entre BFS y DFS es mucho más extensa que una mera cola versus stack.

    PS: También se debe decir que uno puede construir un ejemplo de un gráfico que tendrá un menor consumo de memoria pico en BFS. Por lo tanto, la afirmación sobre una mejor eficiencia espacial de DFS debe verse como algo que podría aplicarse “en promedio” a alguna clase implícita de gráficos “agradables”.

    En DFS, solo necesita espacio para lineal a la profundidad O(log(n)) en un árbol completamente equilibrado, mientras que BFS (búsqueda de amplitud primero) necesita O(n) (la parte más ancha del árbol es la profundidad más baja que tiene un árbol binario n / 2 nodos).

    Ejemplo:

      1 / \ / \ / \ / \ / \ / \ / \ / \ 2 2 / \ / \ / \ / \ / \ / \ / \ / \ 3 3 3 3 / \ / \ / \ / \ / \ / \ / \ / \ 4 4 4 4 4 4 4 4 / \ / \ / \ / \ / \ / \ / \ / \ 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 

    DFS necesita espacio: 4
    BFS necesita en el segundo espacio de la última fila 8

    Y empeora si el factor de ramificación es mayor

    En DFS, el espacio utilizado es O (h) donde h es la altura del árbol.

    En BFS, el espacio utilizado es O (w) donde w es el ‘ancho’ del árbol.

    En árboles binarios típicos (es decir, árboles binarios aleatorios), w = Omega (n) y h = O (sqrt (n)).

    En árboles equilibrados, w = Omega (n) y h = O (log n).