Time and Space Complexity
Lección 7 de 9 del curso Búsqueda en profundidad - Algoritmos de grafos de Coddy.
Complejidad Temporal:
- O(V + E)
- Construir la lista de adyacencia toca cada arista una vez, y el recorrido visita cada vértice y examina cada arista un número constante de veces.
Complejidad Espacial:
- O(V + E)
- La lista de adyacencia almacena cada arista, y el arreglo de visitados y la pila contienen cada uno hasta V vértices.
Resumen:
- DFS explora profundamente primero, retrocediendo cuando se queda sin vecinos no visitados.
- Se ejecuta en tiempo lineal y es la base de muchos algoritmos de grafos.
Pruébalo tú mismo
Esta lección no incluye un desafío de código.
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
Todas las lecciones de Búsqueda en profundidad - Algoritmos de grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity