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