17 - Ordenamiento topológico

El ordenamiento topológico permite listar los vértices de un digrafo respetando la dirección de cada arista. Si existe una arista u → v, entonces u debe aparecer antes que v en el orden. Se usa para planificar tareas, resolver dependencias de software, compilar módulos, orquestar pipelines y más.

17.1 DAG (Directed Acyclic Graph)

El orden topológico solo existe si el grafo es un DAG:

  • Directed: las aristas tienen dirección.
  • Acyclic (no hay ciclos dirigidos).
  • Graph: estructura de nodos y aristas.

Si hay un ciclo, por ejemplo A → B → C → A, no se puede linealizar porque cada vértice depende de otro que vuelve. Cualquier orden topológico es una manera de aplanar el DAG respetando sus dependencias.

17.2 Algoritmo de Kahn (por grados de entrada)

Parte de los vértices con grado de entrada 0 (sin dependencias) y los procesa en una cola.

  1. Reunir todos los vértices con in-degree = 0 y encolarlos.
  2. Mientras la cola no esté vacía:
    • Extraer un vértice v y agregarlo al orden topológico.
    • Eliminar sus aristas salientes, decrementando el in-degree de cada vecino.
    • Si algún vecino queda con in-degree = 0, encolarlo.

Si se procesan todos los vértices, el grafo es un DAG; si quedan sin procesar, existe un ciclo.

Ejemplo (A → C, B → C, C → D):

  • In-degree: A=0, B=0, C=2, D=1.
  • Orden posible: A, B, C, D.

17.3 Algoritmo DFS

Otra forma es usar DFS y apilar nodos al terminar sus vecinos.

  1. Ejecutar DFS.
  2. Al finalizar la exploración de un nodo v, insertarlo al frente de una lista (o pushear en un stack).
  3. Invertir la lista o leer el stack de arriba hacia abajo para obtener el orden topológico.

La intuición: un nodo entra en la lista solo cuando todas sus dependencias ya se resolvieron.

El DFS también permite detectar ciclos con un arreglo de colores: blanco (no visitado), gris (en proceso), negro (finalizado). Una arista hacia un nodo gris indica ciclo.

17.4 Detección de ciclos

  • Kahn: si al terminar quedan nodos con in-degree > 0, hay un ciclo.
  • DFS: una arista hacia un nodo gris (back-edge) revela un ciclo dirigido.
  • Ejemplo de ciclo: Tarea_A → Tarea_B → Tarea_C → Tarea_A; no existe orden válido.

17.5 Usos en dependencias (aplicaciones reales)

  • Compilación de programas: respetar headers y módulos dependientes (ej. A.py, B.py, C.py).
  • Sistemas de paquetes: apt, npm, pip o conda calculan el orden de instalación según dependencias.
  • Construcción de proyectos: Make/CMake/Gradle usan grafos de reglas; compilan y evitan recompilar lo ya actualizado.
  • Cursos y prerrequisitos: determinar el orden posible (Prog I → Prog II → Estructuras de datos → Algoritmos avanzados).
  • Planificación de tareas: flujos de trabajo y pipelines (no hay deploy sin compilar ni testear antes).
  • Procesamiento de imágenes y señales: cada filtro depende de la salida del anterior.
  • Sistemas de versiones y CI/CD: ordenar commits o integraciones en DAGs de builds.

17.6 Algoritmo de Kahn para probar en VSCode

Implementación del algoritmo de Kahn sobre lista de adyacencia (grafos dirigidos). Si hay ciclo, el orden no es posible.

from collections import deque

def agregar_arista_dirigida(g, u, v):
  g[u].append((v, 1))

def orden_topologico_kahn(g):
  indeg = {v: 0 for v in g}
  for u in g:
    for v, _ in g[u]:
      indeg[v] += 1

  cola = deque([v for v in g if indeg[v] == 0])
  orden = []

  while cola:
    u = cola.popleft()
    orden.append(u)
    for v, _ in g[u]:
      indeg[v] -= 1
      if indeg[v] == 0:
        cola.append(v)

  if len(orden) != len(g):
    return None
  return orden

def main():
  g = {i: [] for i in range(6)}
  agregar_arista_dirigida(g, 0, 2)
  agregar_arista_dirigida(g, 0, 3)
  agregar_arista_dirigida(g, 1, 3)
  agregar_arista_dirigida(g, 1, 4)
  agregar_arista_dirigida(g, 3, 5)
  agregar_arista_dirigida(g, 2, 5)

  orden = orden_topologico_kahn(g)
  if orden is None:
    print("Hay un ciclo dirigido, no existe orden topologico.")
  else:
    print("Orden topologico (Kahn):")
    print(" ".join(map(str, orden)))

if __name__ == "__main__":
  main()
Editor online

17.7 Algoritmo DFS (aplicación en Python)

Versión recursiva con detección de ciclos usando colores (0 no visitado, 1 en proceso, 2 finalizado). Si hay back-edge, no existe orden topológico.

def agregar_arista_dirigida(g, u, v):
  g[u].append((v, 1))

def dfs_topo(g, u, color, stack):
  color[u] = 1
  for v, _ in g[u]:
    if color[v] == 0:
      if not dfs_topo(g, v, color, stack):
        return False
    elif color[v] == 1:
      return False
  color[u] = 2
  stack.append(u)
  return True

def orden_topologico_dfs(g):
  color = {v: 0 for v in g}
  stack = []
  for u in g:
    if color[u] == 0:
      if not dfs_topo(g, u, color, stack):
        return None
  stack.reverse()
  return stack

def main():
  g = {i: [] for i in range(6)}
  agregar_arista_dirigida(g, 0, 2)
  agregar_arista_dirigida(g, 0, 3)
  agregar_arista_dirigida(g, 1, 3)
  agregar_arista_dirigida(g, 1, 4)
  agregar_arista_dirigida(g, 3, 5)
  agregar_arista_dirigida(g, 2, 5)

  orden = orden_topologico_dfs(g)
  if orden is None:
    print("Hay un ciclo dirigido, no existe orden topologico.")
  else:
    print("Orden topologico (DFS):")
    print(" ".join(map(str, orden)))

if __name__ == "__main__":
  main()
Editor online
Retornar