Ordenamiento topológico

Carta Común · N.º 408202

Una ordenación topológica (topological sort, topological ordering, topsort o toposort en inglés) de un grafo acíclico dirigido G es una ordenación lineal de todos los nodos de G que satisface que si G contiene la arista dirigida uv entonces el nodo u aparece antes del nodo v. La condición que el grafo no contenga ciclos es importante, ya que no se puede obtener ordenación topológica de grafos que contengan ciclos. Usualmente, para clarificar el concepto se suelen identificar los nodos con tareas a realizar en la que hay una precedencia a la hora de ejecutar dichas tareas. La ordenación topológica por tanto es una lista en orden lineal en que deben realizarse las tareas. Para poder encontrar la ordenación topológica del grafo G deberemos aplicar una modificación del algoritmo de búsqueda en profundidad (DFS).

Leer en Wikipedia