Colocado
Por colocar
Aristas revisadas

  • Actual
  • Libre o en visita
  • Colocado
  • Ciclo

Más sobre el ordenamiento topológico

Ordenamiento topológico

Los calcetines antes que los zapatos, los cimientos antes que las paredes, una asignatura antes de la que la necesita. Un ordenamiento topológico pone los nodos de un grafo con aristas de un solo sentido en una fila donde cada arista apunta hacia delante. Elige el algoritmo de Kahn o el método DFS y avanza paso a paso para ver crecer el orden, y añade un ciclo para ver por qué entonces no hay orden posible. Pulsa Reproducir para ver crecer el orden, o Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto. Cada arista es de un solo sentido, como muestra su flecha: léela como «esto va antes que aquello». Elige el método: el algoritmo de Kahn coloca primero los nodos sin aristas entrantes, y el número de cada nodo es cuántas aristas entrantes le quedan; el método DFS coloca cada nodo delante en cuanto todo lo que va después de él está colocado. La fila bajo el grafo es el orden hasta ahora. Marca Añadir un ciclo para ver cómo lo encuentra cada método. Nuevo grafo crea otro grafo; elige cuántos nodos y aristas tiene. Con el tablero seleccionado, las flechas avanzan o retroceden un paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.

Cómo funciona

  1. Elige el algoritmo de Kahn o el método DFS.
  2. Pulsa Reproducir, o usa Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto.
  3. Observa cómo crece el orden bajo el grafo. Marca Añadir un ciclo para ver cómo lo encuentra cada método.

Algoritmo de Kahn

Cuenta, para cada nodo, cuántas aristas apuntan a él. Un nodo sin ninguna no depende de nada, así que puede ir primero. Coloca ese nodo y quita sus aristas salientes: los nodos a los que apuntaban tienen ahora una arista entrante menos, y algunos pueden llegar a cero y quedar libres. Sigue colocando nodos libres hasta que no quede ninguno. Si algunos nodos nunca quedaron libres, se esperan unos a otros en un ciclo, y no existe orden topológico.

El método DFS

Haz una búsqueda en profundidad desde cada nodo no visitado. Un nodo está terminado cuando todo lo que se alcanza desde él está terminado, así que todo lo que debe ir después de él ya está colocado. Pon cada nodo terminado al principio del orden, y el orden sale correcto. Si la búsqueda sigue una arista hacia un nodo en el que todavía está, esa arista cierra un ciclo, y de nuevo no existe orden.

Preguntas frecuentes

¿Qué es un ordenamiento topológico?

Una ordenación de los nodos de un grafo dirigido en la que cada arista va de un nodo anterior a uno posterior. Si las aristas significan «debe ir antes», es un orden en el que se pueden hacer todas las tareas.

¿Cuándo existe un orden topológico?

Exactamente cuando el grafo no tiene ciclos dirigidos: es un grafo acíclico dirigido, o DAG. Con un ciclo, cada nodo del ciclo tendría que ir antes que sí mismo.

¿Es único el orden topológico?

Normalmente no. Siempre que dos nodos no estén unidos por una cadena de aristas, cualquiera de los dos puede ir primero, así que un grafo puede tener muchos órdenes válidos. El algoritmo de Kahn y el método DFS suelen dar órdenes distintos.

¿Es rápido un ordenamiento topológico?

Ambos métodos revisan cada nodo y cada arista un número fijo de veces, así que el trabajo crece con el número de nodos más el número de aristas.

¿Se envía mi grafo a algún sitio?

No. El grafo se crea y se ordena en tu navegador, y tus últimos ajustes se guardan en el almacenamiento local de este navegador.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Ir al editor