Complejidad Temporal
O(V + E)
El Ordenamiento Topológico produce un ordenamiento lineal de vértices en un Grafo Acíclico Dirigido (DAG) tal que para cada arista dirigida u → v, el vértice u aparece antes que v en el ordenamiento.
Cómo funciona (Algoritmo de Kahn - basado en BFS):
1. Calcular el grado de entrada de cada vértice
2. Agregar todos los vértices con grado de entrada 0 a una cola
3. Mientras la cola no esté vacía:
a. Desencolar un vértice, agregarlo al resultado
b. Para cada arista saliente, decrementar el grado de entrada del vecino
c. Si el grado de entrada de un vecino llega a 0, encolarlo
4. Si todos los vértices fueron procesados, el resultado es un orden topológico válido
Complejidad Temporal: O(V + E)
Complejidad Espacial: O(V)
Aplicaciones:
- Planificación de tareas con dependencias
- Sistemas de compilación (Make, Gradle)
- Planificación de prerrequisitos de cursos
- Resolución de dependencias de paquetes
El Ordenamiento Topológico solo es posible para DAGs (Grafos Acíclicos Dirigidos). Si el grafo tiene un ciclo, no existe un ordenamiento válido.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Ordenamiento Topológico (Algoritmo de Kahn)?
- El Ordenamiento Topológico produce un ordenamiento lineal de vértices en un Grafo Acíclico Dirigido (DAG) tal que para cada arista dirigida u → v, el vértice u aparece antes que v en el ordenamiento.
- ¿Cuál es la complejidad de Ordenamiento Topológico (Algoritmo de Kahn)?
- Tiempo (promedio): O(V + E) · Espacio: O(V)
- ¿Para quién es este visualizador de Ordenamiento Topológico (Algoritmo de Kahn)?
- La visualización de Ordenamiento Topológico (Algoritmo de Kahn) está pensada para nivel avanzado, dentro de la categoría Grafos. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Ordenamiento Topológico (Algoritmo de Kahn)?
- En la misma categoría (Grafos) puedes explorar: Breadth-First Search, Depth-First Search, Dijkstra's Algorithm. Todos tienen visualización interactiva.