algorithm
Primera búsqueda de profundidad

Introducción a la búsqueda en profundidad primero

La búsqueda en profundidad es un algoritmo para atravesar o buscar estructuras de datos de árboles o gráficos. Uno comienza en la raíz y explora en la medida de lo posible a lo largo de cada rama antes de retroceder. Se investigó una versión de la búsqueda en profundidad en el matemático francés del siglo XIX Charles Pierre Trémaux como estrategia para resolver laberintos.

La búsqueda en profundidad es una forma sistemática de encontrar todos los vértices accesibles desde un vértice fuente. Al igual que la búsqueda de amplitud, el DFS atraviesa un componente conectado de un gráfico dado y define un árbol de expansión. La idea básica de la búsqueda en profundidad es explorar metódicamente cada borde. Comenzamos de nuevo desde vértices diferentes según sea necesario. Tan pronto como descubrimos un vértice, DFS comienza a explorar desde él (a diferencia de BFS, que pone un vértice en una cola para que explore más adelante).

Veamos un ejemplo. Atravesaremos este gráfico:

Atravesaremos la gráfica siguiendo estas reglas:

• Empezaremos desde la fuente.
• Ningún nodo será visitado dos veces.
• Los nodos que aún no visitamos, serán de color blanco.
• El nodo que visitamos, pero no visitamos todos sus nodos secundarios, será de color gris.
• Los nodos completamente atravesados ​​serán de color negro.

Vamos a verlo paso a paso:

Podemos ver una palabra clave importante. Eso es backedge . Puedes ver. 5-1 se llama backedge. Esto se debe a que aún no hemos terminado con el nodo 1 , por lo que pasar de otro nodo al nodo 1 significa que hay un ciclo en el gráfico. En DFS, si podemos pasar de un nodo gris a otro, podemos estar seguros de que la gráfica tiene un ciclo. Esta es una de las formas de detectar ciclos en una gráfica. Según el nodo de origen y el orden de los nodos que visitemos, podemos descubrir cualquier borde en un ciclo como backedge . Por ejemplo: si fuimos a 5 de 1 primero, habríamos descubierto 2-1 como backedge.

El borde que tomamos para ir del nodo gris al nodo blanco se llama borde del árbol . Si solo mantenemos el borde del árbol y eliminamos otros, obtendremos el árbol DFS .

En un gráfico no dirigido, si podemos visitar un nodo ya visitado, ese debe ser un backedge . Pero para los gráficos dirigidos, hay que comprobar los colores. Si y solo si podemos pasar de un nodo gris a otro nodo gris, eso se llama backedge .

En DFS, también podemos mantener las marcas de tiempo para cada nodo, que se pueden usar de muchas maneras (por ejemplo: Ordenación topológica).

1. Cuando un nodo v cambia de blanco a gris, el tiempo se registra en d [v] .
2. Cuando un nodo v cambia de gris a negro, el tiempo se registra en f [v] .

Aquí d [] significa tiempo de descubrimiento y f [] significa tiempo de finalización . Nuestro pesudo-código se verá así:

Procedure DFS(G):
for each node u in V[G]
    color[u] := white
    parent[u] := NULL
end for
time := 0
for each node u in V[G]
    if color[u] == white
        DFS-Visit(u)
    end if
end for

Procedure DFS-Visit(u):
color[u] := gray
time := time + 1
d[u] := time
for each node v adjacent to u
    if color[v] == white
        parent[v] := u
        DFS-Visit(v)
    end if
end for
color[u] := black
time := time + 1
f[u] := time

Complejidad:

Cada nodos y aristas se visitan una vez. Entonces, la complejidad de DFS es O (V + E) , donde V denota el número de nodos y E denota el número de bordes.

Aplicaciones de Profundidad Primera Búsqueda:

• Encontrar la ruta más corta de todos los pares en un gráfico no dirigido.
• Ciclo de detección en una gráfica.
• Búsqueda de caminos.
• Clasificación topológica.
• Comprobando si una gráfica es bipartita.
• Encontrar el componente fuertemente conectado.
• Resolviendo puzzles con una solución.