¿Qué es un ordenamiento topológico?

Es un ordenamiento de los vértices de un grafo dirigido tal que para toda arista dirigida de u a v, u aparece antes que v en el ordenamiento — solo posible cuando el grafo no tiene ciclos.

¿Cómo funciona el algoritmo de Kahn?

Encuentra repetidamente un nodo con cero aristas entrantes restantes (sin prerrequisitos sin procesar), lo elimina y lo añade al orden de salida, luego disminuye el grado de entrada de sus vecinos, repitiendo hasta que se procese cada nodo.

¿Qué pasa si el grafo tiene un ciclo?

El algoritmo se atasca — algunos nodos siempre tendrán al menos una arista entrante desde dentro del ciclo, así que nunca son eliminables, y la calculadora informa que no existe ningún orden topológico válido.

¿Es siempre único el orden topológico?

No — cuando varios nodos tienen cero aristas entrantes al mismo tiempo, cualquiera de ellos podría ir después, así que un grafo puede tener varios órdenes topológicos válidos. Esta calculadora elige uno de forma consistente usando desempate alfabético.

¿En qué se diferencia esto del algoritmo de Dijkstra?

El algoritmo de Dijkstra encuentra los caminos más cortos en un grafo ponderado; el ordenamiento topológico encuentra un orden de procesamiento válido en un grafo dirigido basado puramente en la estructura de dependencias, sin ninguna noción de peso o distancia de arista.

¿Qué significa '->' en la entrada de aristas?

Indica dirección — A->B significa que hay una arista dirigida de A a B (A debe ir antes que B), a diferencia del formato no dirigido 'A-B' usado por las otras herramientas de grafos del sitio.

¿Cuántos nodos puede manejar esta calculadora?

Esta calculadora admite hasta 50 nodos, manteniendo instantáneo el algoritmo de Kahn mientras cubre la gran mayoría de los grafos de dependencias introducidos manualmente.

¿Dónde se usa el ordenamiento topológico en la vida real?

Se usa en sistemas de compilación y compiladores (compilando archivos en orden de dependencia), gestores de paquetes (instalando dependencias antes de los paquetes que las necesitan), planificadores de tareas, y el orden de evaluación de fórmulas en hojas de cálculo.

Calculadora de Ordenamiento Topológico — Ordena Tareas Según Sus Dependencias

Nuestra Calculadora de Ordenamiento Topológico encuentra un ordenamiento válido de los nodos de un grafo dirigido tal que toda arista apunte de un nodo anterior a uno posterior — exactamente el ordenamiento que necesitas para programar tareas dependientes — usando el algoritmo de Kahn, e informa claramente cuando no existe tal ordenamiento porque el grafo contiene un ciclo.

Respuesta rápida

Introduce tu grafo dirigido como una lista de aristas para encontrar al instante un orden topológico válido mediante el algoritmo de Kahn, o detectar que un ciclo hace imposible el ordenamiento.

Aristas dirigidas (separadas por comas)

Introduce aristas dirigidas como NodoA->NodoB, p. ej. A->B, A->C, B->D.

Cómo usar Calculadora de Ordenamiento Topológico — Algoritmo de Kahn Online

1
Introduce tu grafo dirigido como una lista de aristas separadas por comas, p. ej. A->B, A->C, B->D.
2
Haz clic en 'Calcular' para encontrar un orden topológico válido.
3
Revisa el orden resultante, o el mensaje de ciclo detectado si no existe ningún orden.

¿Por qué usar Calculadora de Ordenamiento Topológico — Algoritmo de Kahn Online?

Un ordenamiento topológico organiza los nodos de un grafo dirigido acíclico en una línea donde toda arista apunta hacia adelante — exactamente la estructura necesaria para programar tareas con dependencias, compilar archivos en el orden correcto, o resolver el orden de instalación de paquetes. El algoritmo de Kahn lo encuentra directamente: elimina repetidamente cualquier nodo sin aristas entrantes restantes y añádelo al orden, actualizando el grafo restante a medida que avanzas. Si el proceso se queda sin nodos eliminables antes de colocar todos los nodos, el grafo debe contener un ciclo, lo que significa que no existe ningún ordenamiento válido — esta calculadora detecta ese caso explícitamente en lugar de devolver un orden parcial o incorrecto.

Preguntas frecuentes

Herramientas relacionadas

Calculadora de Ruta Más Corta de Dijkstra — Grafos Ponderados Online

Encuentra la ruta más corta y la distancia total entre dos nodos en un grafo ponderado usando el algoritmo de Dijkstra. Calculadora gratuita con una entrada simple de lista de aristas.

Calculadora de Matriz de Adyacencia — Construye una Matriz de Grafo Online

Construye y muestra la matriz de adyacencia de un grafo a partir de una entrada simple de lista de aristas, junto con su secuencia de grados. Calculadora gratuita, ponderada o no ponderada.

Verificador de Camino Hamiltoniano — Visita Cada Nodo una Vez Online

Comprueba si un grafo tiene un camino hamiltoniano — un camino que visita cada nodo exactamente una vez — mediante búsqueda con retroceso. Calculadora gratuita, limitada a grafos de hasta 10 nodos.