depth first search c program traverse graph
Este tutorial cubre la búsqueda en profundidad (DFS) en C ++ en la que un gráfico o árbol se recorre en profundidad. También aprenderá el algoritmo y la implementación de DFS:
La búsqueda en profundidad (DFS) es otra técnica que se utiliza para recorrer un árbol o un gráfico.
DFS comienza con un nodo raíz o un nodo de inicio y luego explora los nodos adyacentes del nodo actual profundizando en el gráfico o en un árbol. Esto significa que en DFS los nodos se exploran en profundidad hasta que se encuentra un nodo sin hijos.
Una vez que se alcanza el nodo hoja, DFS retrocede y comienza a explorar algunos nodos más de manera similar.
=> Tenga cuidado con la guía de formación para principiantes de C ++ aquí.
Lo que vas a aprender:
Primera búsqueda en profundidad (DFS) en C ++
A diferencia de BFS en el que exploramos los nodos a lo ancho, en DFS exploramos los nodos en profundidad. En DFS usamos una estructura de datos de pila para almacenar los nodos que se están explorando. Los bordes que nos llevan a nodos inexplorados se denominan 'bordes de descubrimiento', mientras que los bordes que conducen a nodos ya visitados se denominan 'bordes de bloque'.
A continuación, veremos el algoritmo y el pseudocódigo para la técnica DFS.
Algoritmo DFS
- Paso 1: Inserte el nodo raíz o el nodo inicial de un árbol o gráfico en la pila.
- Paso 2: Saque el elemento superior de la pila y agréguelo a la lista de visitas.
- Paso 3: Busque todos los nodos adyacentes del nodo marcado como visitados y agregue los que aún no se han visitado, a la pila.
- Paso 4 : Repita los pasos 2 y 3 hasta que la pila esté vacía.
Pseudocódigo
El pseudocódigo para DFS se proporciona a continuación.
A partir del pseudocódigo anterior, notamos que el algoritmo DFS se llama de forma recursiva en cada vértice para garantizar que se visiten todos los vértices.
Travesías con ilustraciones
Ilustremos ahora el recorrido DFS de un gráfico. Para mayor claridad, usaremos el mismo gráfico que usamos en la ilustración de BFS.
Sea 0 el nodo inicial o el nodo fuente. Primero, lo marcamos como visitado y lo agregamos a la lista de visitados. Luego empujamos todos sus nodos adyacentes en la pila.
A continuación, tomamos uno de los nodos adyacentes para procesar, es decir, la parte superior de la pila que es 1. Lo marcamos como visitado agregándolo a la lista de visitados. Ahora busque los nodos adyacentes de 1. Como 0 ya está en la lista de visitas, lo ignoramos y visitamos 2, que es la parte superior de la pila.
A continuación, marcamos el nodo 2 como visitado. Su nodo adyacente 4 se agrega a la pila.
A continuación, marcamos 4 que es la parte superior de la pila como visitada. El nodo 4 solo tiene el nodo 2 como su adyacente, que ya está visitado, por lo que lo ignoramos.
En esta etapa, solo el nodo 3 está presente en la pila. Su nodo adyacente 0 ya está visitado, por lo que lo ignoramos. Ahora marcamos 3 como visitado.
Ahora la pila está vacía y la lista visitada muestra la secuencia del recorrido en profundidad primero del gráfico dado.
Si observamos el gráfico dado y la secuencia transversal, notamos que para el algoritmo DFS, de hecho recorremos el gráfico en profundidad y luego retrocedemos nuevamente para explorar nuevos nodos.
Implementación de búsqueda en profundidad
Implementemos la técnica transversal DFS usando C ++.
|_+_| Producción:
Recorrido de profundidad primero para el gráfico dado:
0 1 2 4 3
Una vez más, hemos usado el gráfico en el programa que usamos con fines ilustrativos. Vemos que el algoritmo DFS (separado en dos funciones) se llama de forma recursiva en cada vértice del gráfico para asegurar que se visiten todos los vértices.
Análisis de tiempo de ejecución
La complejidad de tiempo de DFS es la misma que BFS, es decir, O (| V | + | E |) donde V es el número de vértices y E es el número de aristas en un gráfico dado.
Similar a BFS, dependiendo de si el gráfico está poco poblado o densamente poblado, el factor dominante serán los vértices o aristas respectivamente en el cálculo de la complejidad del tiempo.
DFS iterativo
La implementación que se muestra arriba para la técnica DFS es de naturaleza recursiva y usa una pila de llamadas de función. Tenemos otra variación para implementar DFS, es decir, ' Búsqueda iterativa en profundidad ”. En esto, usamos la pila explícita para contener los vértices visitados.
A continuación, mostramos la implementación de DFS iterativo. Tenga en cuenta que la implementación es la misma que la de BFS, excepto el factor de que usamos la estructura de datos de la pila en lugar de una cola.
|_+_| Producción:
Salida de recorrido iterativo de profundidad primero:
0 3 2 4 1
Usamos el mismo gráfico que usamos en nuestra implementación recursiva. La diferencia en la salida se debe a que usamos la pila en la implementación iterativa. Como las pilas siguen el orden LIFO, obtenemos una secuencia diferente de DFS. Para obtener la misma secuencia, es posible que deseemos insertar los vértices en orden inverso.
BFS frente a DFS
Hasta ahora hemos discutido ambas técnicas de recorrido para gráficos, es decir, BFS y DFS.
Ahora veamos las diferencias entre los dos.
| BFS | DFS |
|---|---|
| Significa 'búsqueda primero en amplitud' | Significa 'búsqueda en profundidad' |
| Los nodos se exploran en amplitud nivel por nivel. | Los nodos se exploran en profundidad hasta que solo quedan nodos hoja y luego se retrocede para explorar otros nodos no visitados. |
| BFS se realiza con la ayuda de la estructura de datos de la cola. | DFS se realiza con la ayuda de la estructura de datos de la pila. |
| Rendimiento más lento. | Más rápido que BFS. |
| Útil para encontrar el camino más corto entre dos nodos. | Se utiliza principalmente para detectar ciclos en gráficos. |
Aplicaciones de DFS
- Detección de ciclos en el gráfico: Si encontramos un borde posterior mientras realizamos DFS en un gráfico, podemos concluir que el gráfico tiene un ciclo. Por lo tanto, DFS se usa para detectar los ciclos en un gráfico.
- Pathfinding: Dados dos vértices xey, podemos encontrar la ruta entre xey usando DFS. Comenzamos con el vértice x y luego empujamos todos los vértices en el camino hacia la pila hasta que encontramos y. El contenido de la pila da la ruta entre xey.
- Árbol de expansión mínimo y camino más corto: El recorrido DFS del gráfico no ponderado nos da un árbol de expansión mínimo y la ruta más corta entre los nodos.
- Clasificación topológica: Usamos la clasificación topológica cuando necesitamos programar los trabajos a partir de las dependencias dadas entre trabajos. En el campo de la informática, lo usamos principalmente para resolver dependencias de símbolos en enlazadores, serialización de datos, programación de instrucciones, etc. DFS se usa ampliamente en la clasificación topológica.
Conclusión
En el último par de tutoriales, exploramos más sobre las dos técnicas transversales para gráficos, es decir, BFS y DFS. Hemos visto las diferencias y las aplicaciones de ambas técnicas. BFS y DFS básicamente logran el mismo resultado de visitar todos los nodos de un gráfico, pero difieren en el orden de salida y la forma en que se hace.
También hemos visto la implementación de ambas técnicas. Mientras que BFS usa una cola, DFS usa pilas para implementar la técnica. Con esto concluimos el tutorial sobre técnicas transversales para grafos. También podemos usar BFS y DFS en árboles.
cómo escribir una muestra de plan de prueba
Aprenderemos más sobre los árboles de expansión y un par de algoritmos para encontrar la ruta más corta entre los nodos de un gráfico en nuestro próximo tutorial.
=> Consulte aquí para explorar la lista completa de tutoriales de C ++.
Lectura recomendada
- Programa C ++ Breadth First Search (BFS) para recorrer un gráfico o árbol
- Árbol de búsqueda binaria C ++: implementación y operaciones de BST con ejemplos
- Estructura de datos de árbol B y árbol B + en C ++
- Tutoriales detallados de Eclipse para principiantes
- Estructura de datos de árbol binario en C ++
- Implementación de gráficos en C ++ mediante lista de adyacencia
- Estructura de datos de montón y árbol AVL en C ++
- Las 12 mejores herramientas para crear gráficos de líneas para crear gráficos de líneas impresionantes (RANKINGS 2021)