Aplicaciones de la primera búsqueda en profundidad

 

La búsqueda en profundidad (DFS) es un algoritmo (o técnica) para recorrer un gráfico. DFS utiliza una estructura de datos de pila para el recorrido. Un gráfico puede tener más de un recorrido DFS.

Los siguientes son los problemas que usan DFS como bloque de construcción.  

1) Detección de ciclo en un gráfico 
Un gráfico tiene ciclo si y solo si vemos un borde posterior durante DFS. Entonces podemos ejecutar DFS para el gráfico y verificar los bordes posteriores. (Ver esto para más detalles) 

2) Búsqueda de ruta 
Podemos especializar el algoritmo DFS para encontrar una ruta entre dos vértices dados u y z. 
i) Llame a DFS(G, u) con u como vértice inicial. 
ii) Use una pila S para realizar un seguimiento de la ruta entre el vértice inicial y el vértice actual. 
iii) Tan pronto como se encuentre el vértice de destino z, devuelva la ruta como el 
contenido de la pila 

Vea esto para más detalles. 

3) Clasificación 
topológica La clasificación topológica se utiliza principalmente para programar trabajos a partir de las dependencias dadas entre los trabajos. En informática, las aplicaciones de este tipo surgen en la programación de instrucciones, el ordenamiento de la evaluación de celdas de fórmulas al volver a calcular valores de fórmulas en hojas de cálculo, la síntesis lógica, la determinación del orden de las tareas de compilación a realizar en archivos MAKE, la serialización de datos y la resolución de dependencias de símbolos en enlazadores [2]. ]. 

4) Para probar si un gráfico es bipartito 
. Podemos aumentar BFS o DFS cuando descubrimos un nuevo vértice por primera vez, colorearlo opuesto a sus padres, y para cada borde, comprobar que no une dos vértices del mismo color. ¡El primer vértice en cualquier componente conectado puede ser rojo o negro! Vea esto para más detalles. 

5) Encontrar componentes fuertemente conexos de un gráfico Un gráfico dirigido se llama fuertemente conectado si hay un camino desde cada vértice en el gráfico a todos los demás vértices. (Vea esto para un algoritmo basado en DFS para encontrar componentes fuertemente conectados) 

6) Resolver acertijos con una sola solución , como laberintos. (DFS se puede adaptar para encontrar todas las soluciones a un laberinto al incluir solo los Nodes en la ruta actual en el conjunto visitado). 

 

Fuentes:  
http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/LEC/LECTUR16/NODE16.HTM  
http://en.wikipedia.org/wiki/Depth-first_search  
http://www. personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/  
depthSearch.htm http://ww3.algorithmdesign.net/handouts/DFS.pdf
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *