10.1 Definizione di ordinamento topologico
Ordinamento topologico — è un ordinamento lineare dei vertici di un grafo diretto aciclico (DAG) tale che per ogni arco (u, v) il vertice u preceda il vertice v. Questa disposizione è possibile solo per un DAG e non può essere applicata ai grafi che contengono cicli.
Che ne pensi della definizione? Se l'hai capita al primo colpo, probabilmente hai già tanta esperienza con gli algoritmi.
Spiegato in modo semplice, funziona così: hai una lista di compiti (i vertici del grafo) e una lista di dipendenze tra di loro (le frecce del grafo). Disponi i compiti (vertici) in modo che tutti i compiti da cui dipende il "compito A" vengano eseguiti prima. Tutto chiaro ora, vero? Altro che "ordinamento lineare dei vertici di un grafo diretto aciclico"...
L'ordinamento topologico è un algoritmo molto importante nella pratica, tanto da avere un proprio nome anziché quello del suo autore. Vediamo insieme dove può essere utile:
Applicazioni:
1. Programmazione dei task (Task Scheduling):
Determinare l'ordine di esecuzione dei task dipendenti in modo che ogni task venga eseguito solo dopo che tutte le sue dipendenze siano state completate.
Esempio:
Organizzare i progetti in un sistema di gestione dei progetti.
2. Compilazione del codice:
Determinare l'ordine di compilazione di moduli o file di codice sorgente, che dipendono l'uno dall'altro.
Esempio:
Ottimizzazione della costruzione del software nei sistemi di build (ad esempio, Makefile).
3. Risoluzione delle dipendenze nei package manager:
Ordinare i pacchetti in modo che tutte le dipendenze vengano installate prima del pacchetto stesso.
Esempio:
Rendere più semplice il processo di installazione dei software nei package manager (ad esempio, npm, pip, apt).
4. Ottimizzazione delle rotte:
Determinare l'ordine delle tappe o delle azioni da svolgere, tenendo conto delle dipendenze tra di loro.
Esempio:
Logistica e pianificazione delle rotte di consegna dei prodotti.
Complessità temporale e spaziale dell'ordinamento topologico:
Complessità temporale:
Entrambi gli algoritmi principali di ordinamento topologico (DFS e algoritmo di Kahn)
hanno una complessità temporale di O(V + E), dove V è il numero di vertici e
E è il numero di archi nel grafo.
Complessità spaziale:
La complessità spaziale di entrambi gli algoritmi è O(V + E), perché
è necessario memorizzare il grafo e anche gli array per tenere traccia dei vertici
visitati e dei predecessori.
10.2 Implementazione tramite ricerca in profondità (DFS)
L'ordinamento topologico può essere eseguito in vari modi, uno dei quali si basa sulla ricerca in profondità — DFS. L'algoritmo DFS per l'ordinamento topologico utilizza uno stack per tenere traccia dei nodi completati.
Esempio di implementazione:
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] # Risultato in ordine inverso
# Esempio d'uso:
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
result = topological_sort_dfs(graph)
print("Ordinamento topologico:", result)
Output:
Ordinamento topologico: ['B', 'D', 'F', 'G', 'A', 'C', 'E', 'H']
10.3 Implementazione: algoritmo di Kahn
Un altro approccio si chiama algoritmo di Kahn (Kahn's Algorithm). L'algoritmo di Kahn utilizza il concetto di gradi in ingresso per i vertici per l'ordinamento topologico.
Esempio di implementazione:
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("Il grafo contiene un ciclo")
# Esempio d'uso:
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
result = topological_sort_kahn(graph)
print("Ordinamento topologico:", result)
Output:
Ordinamento topologico: ['A', 'B', 'D', 'C', 'E', 'H', 'F', 'G']
GO TO FULL VERSION