Algoritmo di Kahn: ordinamento topologico BFS
Calcoli i gradi entranti di tutti i nodi, inserisca in coda quelli con grado entrante zero ed elabori la coda per produrre un ordine topologico rilevando al contempo i cicli.
Algoritmo di Kahn: ordinamento topologico BFS è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Che cos'è l'ordinamento topologico?
Un ordinamento topologico di un grafo aciclico diretto (DAG) è un ordinamento dei suoi nodi tale che ogni arco orientato u → v implichi che u venga prima di v nell'ordinamento. Rappresenta un ordine di esecuzione valido per attività con dipendenze, come nei sistemi di build, nella pianificazione dei corsi o nella gestione dei pacchetti. Solo i DAG ammettono ordinamenti topologici validi; un ciclo li rende impossibili.
Algoritmo di Kahn: idea fondamentale
L'algoritmo di Kahn è un approccio basato sulla BFS all'ordinamento topologico. L'idea chiave è che un nodo con grado entrante 0 (senza prerequisiti) può essere inserito per primo nell'ordinamento. Dopo averlo inserito, lo rimuova e decrementi il grado entrante dei suoi vicini. I nuovi nodi con grado entrante pari a zero diventano disponibili. Ripeta finché tutti i nodi sono stati inseriti oppure viene rilevato un ciclo (rimangono nodi con grado entrante diverso da zero).
Calcolo del grado entrante
Per prima cosa, costruisca la lista di adiacenza e calcoli il grado entrante (il numero di archi entranti) per ogni nodo. I nodi con grado entrante 0 sono i punti di partenza: non hanno dipendenze. Per un grafo con archi [(0,1),(0,2),(1,3),(2,3)], i gradi entranti sono: 0→0, 1→1, 2→1, 3→2. Solo il nodo 0 inizia con grado entrante 0.
from collections import deque, defaultdict
def compute_in_degree(n, edges):
in_degree = [0] * n
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
return graph, in_degree
graph, ind = compute_in_degree(4, [(0,1),(0,2),(1,3),(2,3)])
print('In-degrees:', ind) # [0, 1, 1, 2]Implementazione dell'algoritmo di Kahn
Accodi tutti i nodi con grado entrante pari a zero in una coda. Elabori ogni nodo: lo aggiunga al risultato, quindi decrementi il grado entrante di ciascun vicino e lo accodi se raggiunge 0. Se la lista dei risultati contiene meno nodi del grafo, esiste un ciclo: alcuni nodi non hanno mai potuto essere estratti dalla coda.
from collections import deque, defaultdict
def kahn_topological_sort(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(i for i in range(n) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
if len(order) == n:
return order # valid topological sort
return [] # cycle detected
print(kahn_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))Rilevamento dei cicli con Kahn
L'algoritmo di Kahn offre un rilevamento dei cicli integrato: se len(order) < n, alcuni nodi non sono mai stati aggiunti alla coda perché il loro grado entrante non ha mai raggiunto 0; fanno parte di un ciclo. È più semplice che mantenere un array dei visitati codificato per colori. Restituisca una lista vuota per segnalare l'esistenza di un ciclo.
# Cyclic graph: 0->1->2->0
edges_cycle = [(0,1),(1,2),(2,0)]
result = kahn_topological_sort(3, edges_cycle)
print(result) # [] (cycle detected)
# Acyclic graph
edges_dag = [(0,1),(1,2)]
result = kahn_topological_sort(3, edges_dag)
print(result) # [0, 1, 2]Complessità temporale e spaziale
L'algoritmo di Kahn elabora ogni nodo una volta (viene estratto dalla coda una volta) e ogni arco una volta (il grado entrante viene decrementato una volta). Complessità temporale: O(V + E). Spazio: O(V + E) per la lista di adiacenza e l'array dei gradi entranti, più O(V) per la coda. È ottimale: per produrre un ordinamento valido è necessario almeno leggere tutti i nodi e gli archi.
Ordinamento topologico lessicograficamente minimo
L'algoritmo di Kahn con un min-heap al posto di una coda produce l'ordinamento topologico lessicograficamente minimo. Sostituisca deque con heapq: inserisca (node) e elabori sempre per primo il nodo disponibile più piccolo. In questo modo si garantisce l'ordinamento valido lessicograficamente minimo tra tutti i possibili ordinamenti topologici.
import heapq
from collections import defaultdict
def kahn_lex_order(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
heap = [i for i in range(n) if in_degree[i] == 0]
heapq.heapify(heap)
order = []
while heap:
node = heapq.heappop(heap)
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
heapq.heappush(heap, nxt)
return order if len(order) == n else []
print(kahn_lex_order(6, [(5,2),(5,0),(4,0),(4,1),(2,3),(3,1)]))Applicazione: Course Schedule I
Course Schedule (LeetCode 207): dati n corsi e i relativi prerequisiti, è possibile completarli tutti? Modelli i prerequisiti come archi orientati e verifichi se esiste un ordinamento topologico valido (cioè se non ci sono cicli). Restituisca True se l'algoritmo di Kahn produce un ordinamento di lunghezza n, False se viene rilevato un ciclo.
from collections import deque, defaultdict
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites: # b must be taken before a
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
count = 0
while queue:
node = queue.popleft()
count += 1
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return count == numCourses
print(canFinish(2, [[1,0]])) # True
print(canFinish(2, [[1,0],[0,1]])) # False (cycle)Applicazione: Course Schedule II
Course Schedule II (LeetCode 210): restituisca l'ordine effettivo in cui seguire i corsi. Come sopra, ma restituisca la lista order invece di un booleano. Se esiste un ciclo, restituisca una lista vuota. In questo modo l'output di Kahn viene utilizzato direttamente come risposta.
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))Pianificazione parallela delle attività
Un uso più avanzato: dati alcuni compiti con dipendenze, trovi il numero minimo di «turni» necessari se i compiti senza dipendenze possono essere eseguiti in parallelo. Elabori Kahn per livelli (in modo simile all'ordine a livelli della BFS): accodi tutti i nodi con grado entrante pari a zero, elabori l'intera coda corrente come un unico turno, quindi accodi i nodi che sono diventati disponibili come turno successivo. Conteggi i turni.
from collections import deque, defaultdict
def min_rounds(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(i for i in range(n) if in_degree[i] == 0)
rounds = 0
while queue:
rounds += 1
for _ in range(len(queue)): # process current level
node = queue.popleft()
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return rounds
print(min_rounds(4, [(0,2),(1,2),(2,3)])) # 3Ordinamento topologico e DP sui DAG
L'ordinamento topologico abilita la programmazione dinamica sui DAG: elabori i nodi nell'ordine topologico e, quando calcola dp[v], tutti i valori dp[u] dei predecessori sono già definitivi. Questo combina l'ordinamento topologico con la DP per problemi come il percorso massimo in un DAG, il costo minimo per raggiungere tutti i nodi o il profitto massimo ottenibile da una catena di dipendenze. L'ordinamento garantisce che il valore DP di ogni nodo venga calcolato esattamente una volta, dopo tutte le sue dipendenze.
from collections import deque, defaultdict
def longest_path_dag(V, edges):
graph = defaultdict(list)
in_degree = [0] * V
for u, v, w in edges:
graph[u].append((v, w))
in_degree[v] += 1
queue = deque(i for i in range(V) if in_degree[i] == 0)
dp = [0] * V
while queue:
u = queue.popleft()
for v, w in graph[u]:
dp[v] = max(dp[v], dp[u] + w)
in_degree[v] -= 1
if in_degree[v] == 0: queue.append(v)
return max(dp)
print(longest_path_dag(4, [(0,1,3),(0,2,2),(1,3,4),(2,3,1)])) # 7Verifica rapida
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: l'algoritmo di Kahn calcola l'ordinamento topologico rimuovendo iterativamente con la BFS i nodi con grado entrante pari a zero, il rilevamento dei cicli è integrato: se len(order) < n, esiste un ciclo e sostituire la coda con un min-heap produce l'ordinamento topologico lessicograficamente minimo. Ora esploreremo l'ordinamento topologico basato sulla visita DFS in post-ordine come alternativa a Kahn.
Domande Frequenti
La lezione «Algoritmo di Kahn: ordinamento topologico BFS» è gratuita?
Sì — il testo completo di «Algoritmo di Kahn: ordinamento topologico BFS» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Algoritmo di Kahn: ordinamento topologico BFS»?
Calcoli i gradi entranti di tutti i nodi, inserisca in coda quelli con grado entrante zero ed elabori la coda per produrre un ordine topologico rilevando al contempo i cicli. Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Algoritmo di Kahn: ordinamento topologico BFS»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Algoritmo di Kahn: ordinamento topologico BFS
- Ordinamento topologico DFS post-order
- Course Schedule I e II
- Componenti fortemente connesse con Kosaraju