Búsqueda en profundidad DFS en Python
DFS utiliza recursión o un stack explícito.
¿Qué es Búsqueda en profundidad DFS en Python?
DFS utiliza recursión o un stack explícito.
Sigue un camino antes de retroceder.
¿Cuándo se utiliza?
- Comprender algoritmos y estructuras de datos.
- Observar cada paso y tratar casos límite.
- Comparar tiempo de ejecución y memoria.
Visualizador de Búsqueda en profundidad DFS en Python
O(V+E)Usa Reproducir o Paso para seguir cada comparación y movimiento de datos.
Código de ejemplo
main.py
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
def depth_first(node, visited=None):
visited = visited or set()
visited.add(node)
order = [node]
for neighbor in graph[node]:
if neighbor not in visited:
order.extend(depth_first(neighbor, visited))
return order
print(depth_first("A"))Resultado esperado
['A', 'B', 'D', 'C', 'E']Cómo funciona
Cada vértice y arista se procesa como máximo una vez: O(V+E).
Cambia los valores y ejecuta el programa en el compilador Python online de CodeUtility sin instalar Python.
Ejercicios prácticos
Modifica las entradas y prueba casos límite antes de usar conjuntos de datos mayores.
- Prueba una entrada vacía, un elemento y duplicados.
- Muestra el estado después de cada paso.
- Compara el rendimiento con otra solución.