10.1 Definición de Ordenación Topológica
Ordenación topológica es un orden lineal de los vértices de un grafo dirigido acíclico (DAG), tal que para cada arista (u, v), el vértice u precede al vértice v. Este ordenamiento es posible solo para DAG y no se puede realizar en grafos que contengan ciclos.
¿Qué tal la definición? Si la entendiste a la primera, probablemente ya tienes bastante experiencia con algoritmos.
En palabras simples sería así: tienes una lista de tareas (vértices del grafo) y una lista de dependencias entre ellas (flechas en el grafo). Organiza las tareas (vértices) de tal manera que todas las tareas de las que dependa "la tarea A" se realicen antes que ella. Ahora está todo claro, y no como "orden lineal de los vértices de un grafo dirigido acíclico"...
Ordenación topológica es un algoritmo muy importante en la práctica, por eso tiene su propio nombre, y no solo el del autor. Vamos a ver dónde se usa:
Aplicación:
1. Planificación de tareas (Task Scheduling):
Determinación del orden de ejecución de tareas dependientes para que cada tarea se ejecute después de todas sus dependencias.
Ejemplo:
Planificación de proyectos en un sistema de gestión de proyectos.
2. Compilación de código:
Determinación del orden de compilación de módulos o archivos de código fuente que dependen entre sí.
Ejemplo:
Optimización de la construcción de software en sistemas de build (por ejemplo, Makefile).
3. Resolución de dependencias en gestores de paquetes:
Ordenación de paquetes para que todas las dependencias se instalen antes de instalar el paquete mismo.
Ejemplo:
Simplificación del proceso de instalación de software en gestores de paquetes (por ejemplo, npm, pip, apt).
4. Optimización de rutas:
Determinación del orden para visitar puntos o realizar acciones, considerando las dependencias entre ellos.
Ejemplo:
Logística y planificación de rutas de entrega de mercancías.
Complejidad temporal y espacial de la ordenación topológica:
Complejidad temporal:
Ambos algoritmos principales de ordenación topológica (DFS y el algoritmo de Kahn) tienen una complejidad temporal de O(V + E), donde V es el número de vértices y E es el número de aristas en el grafo.
Complejidad espacial:
La complejidad espacial de ambos algoritmos es O(V + E), ya que se requiere almacenar el grafo, así como matrices para rastrear los vértices visitados y los predecesores.
10.2 Implementación a través de búsqueda en profundidad (DFS)
La ordenación topológica se puede realizar de diferentes maneras, una de ellas se basa en la búsqueda en profundidad — DFS. El algoritmo DFS para la ordenación topológica utiliza una pila para rastrear los nodos completados.
Ejemplo de implementación:
def topological_sort_dfs(graph):
def dfs(vertex, visited, stack):
visited.add(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs(neighbor, visited, stack)
stack.append(vertex)
visited = set()
stack = []
for vertex in graph:
if vertex not in visited:
dfs(vertex, visited, stack)
return stack[::-1] # Resultado en orden inverso
# Ejemplo de uso:
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
result = topological_sort_dfs(graph)
print("Ordenación topológica:", result)
Salida:
Ordenación topológica: ['B', 'D', 'F', 'G', 'A', 'C', 'E', 'H']
10.3 Implementación: algoritmo de Kahn
Otro enfoque se llama el algoritmo de Kahn (Kahn's Algorithm). El algoritmo de Kahn para la ordenación topológica utiliza el concepto de grados de entrada de los vértices.
Ejemplo de implementación:
from collections import deque, defaultdict
def topological_sort_kahn(graph):
in_degree = {u: 0 for u in graph}
for u in graph:
for v in graph[u]:
in_degree[v] += 1
queue = deque([u for u in graph if in_degree[u] == 0])
top_order = []
while queue:
u = queue.popleft()
top_order.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
if len(top_order) == len(in_degree):
return top_order
else:
raise ValueError("El grafo contiene un ciclo")
# Ejemplo de uso:
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
result = topological_sort_kahn(graph)
print("Ordenación topológica:", result)
Salida:
Ordenación topológica: ['A', 'B', 'D', 'C', 'E', 'H', 'F', 'G']
GO TO FULL VERSION