DFS se puede implementar de dos formas: iterativa y recursiva. Aquí, te mostraré cómo hacerlo de forma recursiva ya que, en mi humilde opinión, es más fácil de entender y codificar. Esta también es una oportunidad fantástica para aprender cómo funciona la recursividad si aún no estás familiarizado con ella. La implementación de DFS será en Python puro.
A continuación hay un código para el propio algoritmo DFS.
Hay tres entradas a la función: un conjunto de nodos visitados (generalmente inicialmente vacíos), una definición de gráfico y un nodo inicial. La lógica es simple, pero efectiva:
1. Primero, verificamos si ya hemos visitado un nodo determinado.
a. En caso afirmativo, omita verificar sus vecinos.
b. Si no, imprima el nodo y comience a visitar sus vecinos (el “bucle for”)
2. Repita hasta que todos los nodos estén en la lista de nodos visitados.
En este caso, la función devuelve Ninguno (efectivamente nada) porque imprime los nodos visitados y los escribe en el conjunto definido externamente. Podemos cambiar su comportamiento para devolver un conjunto de todos los nodos visitados sin imprimir valores como ese:
Ejemplo 1
Primero, debemos definir nuestro gráfico ejemplar. Para ello, usaremos la matriz de adyacencia como diccionario de Python. En cada par clave-valor, una clave es un nodo y un valor es una lista de nodos conectados a ella (vecinos).
A continuación se muestra el código que crea el primer gráfico ejemplar en la memoria de la computadora. En este caso, es un gráfico dirigido (para mayor claridad y simplicidad), pero DFS también funciona bien para los no dirigidos.
Después de ejecutar un comando de llamada de función, la salida es una serie de nodos que fueron visitados:
O con la versión alternativa del código como se muestra a continuación. Aquí podemos simplemente hacer un pequeño cambio en la entrada para no usar ninguna variable global y pasar un conjunto vacío directamente. La salida entonces es:
Visualicemos cómo se construye paso a paso una pila de funciones y un conjunto final. Esto se muestra en la siguiente animación.
Ejemplo 2
En este ejemplo, construiremos y recorreremos un tipo especial de gráfico: un árbol de decisión. A continuación se muestra una definición del gráfico.
Después de ejecutar DFS en este gráfico, el resultado es:
La siguiente animación muestra cómo se ve el gráfico y cómo lo atravesó DFS.
Resumen
Depth First Search es un algoritmo esencial en la teoría de grafos, ampliamente utilizado en múltiples dominios, desde redes sociales hasta árboles de decisión. Su naturaleza recursiva hace que sea fácil de entender e implementar, como lo demuestran los ejemplos de este artículo. La simplicidad de DFS, junto con su capacidad para explorar eficientemente todos los nodos en un gráfico, lo convierte en una herramienta poderosa para resolver diversos problemas computacionales. Comprender cómo funciona DFS sienta las bases para dominar otros algoritmos como Breadth First Search (BFS) y algoritmos de búsqueda de rutas como Dijkstra o A*.
Intente experimentar con gráficos más grandes y complejos y explore cómo se comportan con diferentes estructuras de datos. En artículos futuros, exploraremos otros métodos transversales como BFS e investigaremos más a fondo sus casos de uso, ventajas y limitaciones.
Siga practicando y superando sus límites, y pronto los algoritmos gráficos como DFS se convertirán en algo natural. ¡Feliz codificación!
Referencias
[1] Tsok, Samuel y Yakubu, Oseas y Salomón, Rwat. (2023). Modelos gráficos de redes sociales aplicados a Facebook y grupos de Facebook Messenger. Revista Internacional de Ingeniería y Ciencias de la Computación. vol. 9. Pág. 1. 10.56201/ijcsmt.v9.no1.2023.pg1.12. [link]
[2] Tianlun Dai, Wenchao Zheng, Jiayue Sun, Cun Ji, Tao Zhou, Mingtong Li, Wei Hu, Ziqiang Yu, Planificación continua de rutas sobre un gráfico dinámico en tiempo real, Procedia Computer Science, volumen 174, 2020 [link]