Grafi e algoritmi fondamentali: il vocabolario di base

Cos’è un grafo, come metterlo in memoria, e perché l’ordinamento topologico — disporre cose rispettando le loro dipendenze — è lo stesso identico problema in un build system, in un package manager e nella backpropagation di una rete neurale.

Perché questo capitolo

Quasi ogni struttura interessante che un sistema software incontra è un grafo. Un filesystem è un grafo (le directory contengono file e altre directory). Le dipendenze di un progetto sono un grafo (il pacchetto A richiede B, che richiede C). Una mappa stradale è un grafo. Una conversazione tra agenti è un grafo. Una rete neurale, durante il training, è un grafo. La cronologia di Git è un grafo. Quando un concetto ricorre con questa insistenza, conviene avere un vocabolario preciso per parlarne — e gli algoritmi standard per manipolarlo.

Questo capitolo è il punto di riferimento sulle basi: cosa sia un grafo, quali tipi esistono, come rappresentarlo in memoria, e quali sono gli algoritmi fondamentali che ogni sviluppatore dovrebbe poter riconoscere quando li incontra mascherati dentro un sistema più grande. Tre algoritmi di attraversamento o cammino — BFS, DFS, Dijkstra — hanno già un capitolo dedicato e qui vengono solo inquadrati nel contesto più ampio. Il cuore nuovo è l’ordinamento topologico: il problema di mettere in fila degli elementi rispettando un insieme di vincoli di precedenza.

L’ordinamento topologico merita attenzione per un motivo che va oltre l’informatica accademica. È lo stesso problema che risolve make quando decide in che ordine compilare i file, che risolve pip quando installa le dipendenze, che risolve un foglio di calcolo quando ricalcola le celle, e che risolve un framework di deep learning quando esegue la forward e la backward pass di una rete. Vedere che sono lo stesso problema — e che un solo algoritmo da trenta righe li copre tutti — è uno di quei momenti in cui l’informatica mostra la sua economia di mezzi.

Contesto

La teoria dei grafi ha una data di nascita precisa e una storia raccontabile. Nel 1735 Leonhard Euler (matematico svizzero, 1707-1783, uno dei più prolifici della storia) affronta un rompicapo cittadino: la città prussiana di Königsberg è attraversata da un fiume, con due isole collegate alle rive e tra loro da sette ponti. Esiste una passeggiata che attraversi ogni ponte esattamente una volta? Euler fa un’astrazione decisiva: il percorso dentro ogni massa di terra è irrilevante, conta solo la sequenza di ponti. Riduce la città a quattro punti (le masse di terra) e sette collegamenti (i ponti), e dimostra che la passeggiata è impossibile. Il suo “Solutio problematis ad geometriam situs pertinentis”, presentato all’Accademia di San Pietroburgo il 26 agosto 1735 e pubblicato nel 1741, contiene il primo teorema della teoria dei grafi: un percorso che attraversi ogni arco una volta sola esiste solo se al più due nodi hanno un numero dispari di archi.

L’astrazione di Euler — punti e collegamenti, dimenticando tutto il resto — è esattamente ciò che chiamiamo grafo. Da quel rompicapo nasce una disciplina che oggi modella reti sociali, circuiti, mappe, dipendenze software e architetture di reti neurali.

Gli algoritmi che vedremo arrivano molto dopo, con l’informatica. Arthur B. Kahn pubblica nel 1962 “Topological sorting of large networks” su Communications of the ACM: l’algoritmo per ordinare grandi reti di attività con dipendenze, motivato dal project management. Robert Tarjan (informatico americano, Turing Award 1986) pubblica nel 1972 “Depth-First Search and Linear Graph Algorithms” su SIAM Journal on Computing, il paper che trasforma DFS da curiosità da labirinto in framework generale, da cui discende una seconda strada all’ordinamento topologico. Edsger Dijkstra, Richard Bellman, Lester Ford, Joseph Kruskal e Robert Prim completano, tra la fine degli anni ‘50 e gli anni ‘60, il nucleo degli algoritmi di grafo che ancora oggi sono materiale da primo anno e infrastruttura da produzione.

Nella wiki, questo capitolo sta a monte di search-bfs-dfs e search-a-star: quelli scavano in profondità su attraversamenti e cammini minimi informati, questo fornisce il vocabolario e l’algoritmo — l’ordinamento topologico — che gli altri due non trattano.

L’intuizione

Due angoli per entrare nel concetto, prima di qualunque formalismo.

Angolo 1 — il grafo come mappa di relazioni

Un grafo è la struttura dati che si usa quando la cosa importante non sono gli oggetti, ma le relazioni tra gli oggetti. Una lista dice “ecco delle cose, in un ordine”. Una tabella dice “ecco delle cose, ognuna con dei campi”. Un grafo dice “ecco delle cose, ed ecco chi è collegato a chi”.

Tre esempi della stessa idea. In un social network le persone sono i nodi e le amicizie sono gli archi: la domanda interessante non è “quante persone ci sono” ma “quanto sei distante da quella persona, attraverso amici comuni”. In una mappa stradale gli incroci sono i nodi e le strade gli archi: la domanda interessante è “qual è il percorso più breve”. In un progetto software i moduli sono i nodi e le dipendenze sono gli archi: la domanda interessante è “in che ordine posso compilare senza rompere niente”.

Ogni volta che ti accorgi di star disegnando frecce tra scatole su una lavagna, stai disegnando un grafo. Il valore della teoria è che quelle frecce e quelle scatole, una volta formalizzate, ereditano decenni di algoritmi pronti.

Angolo 2 — il DAG come ordine parziale

C’è un secondo angolo, più astratto ma cruciale per la seconda metà del capitolo. Un tipo speciale di grafo — il DAG, grafo diretto aciclico — è il modo naturale di rappresentare un ordine parziale: un insieme di vincoli del tipo “X deve venire prima di Y”, dove però non tutte le coppie sono vincolate.

Pensa a vestirsi al mattino. Le mutande vanno prima dei pantaloni. I calzini vanno prima delle scarpe. La maglietta va prima del maglione. Ma calzini e maglietta non hanno alcun ordine relativo: puoi metterli in qualsiasi sequenza. Questo è un ordine parziale: alcune coppie sono vincolate, altre libere. Disegna una freccia “deve precedere” da ogni capo a quelli che dipendono da lui e ottieni un DAG.

L’ordinamento topologico è la domanda: data questa rete di vincoli parziali, produci una sequenza totale — una vestizione completa, un capo dopo l’altro — che non violi nessun vincolo. La parola “aciclico” è essenziale: se i vincoli contenessero un ciclo (“A prima di B, B prima di C, C prima di A”) nessuna sequenza li soddisferebbe.

Angolo 3 — lo stesso algoritmo, tante maschere

C’è un terzo modo di guardare gli algoritmi di questo capitolo, ed è il più utile per chi scrive software. La maggior parte di essi è la stessa procedura vista in search-bfs-dfs: mantieni una collezione di nodi “da trattare”, ne estrai uno, lo processi, aggiungi alla collezione i nuovi nodi che ne risultano, ripeti. Cambia solo come scegli il prossimo nodo.

Se la collezione è una coda FIFO, esce sempre il più vecchio: ottieni BFS. Se è una pila LIFO, esce il più recente: ottieni DFS. Se è una coda a priorità ordinata sulla distanza accumulata, esce il più vicino: ottieni Dijkstra. Se la priorità è “distanza accumulata più stima del residuo”, ottieni A*. Se la collezione contiene i nodi a in-degree zero, ottieni l’ordinamento topologico di Kahn. Lo scheletro è invariante; la politica di selezione è il parametro che genera un’intera famiglia di algoritmi. Riconoscere questo scheletro condiviso è ciò che permette di leggere un sistema sconosciuto e dire “questo, sotto la maschera, è un BFS con una priorità in più”. Tenere a mente questi tre angoli — relazioni, ordine parziale, scheletro condiviso — basta per il resto del capitolo.

La meccanica

Il vocabolario formale

Un grafo è una coppia $G = (V, E)$ , dove $V$ è l’insieme dei vertici (o nodi) ed $E$ è l’insieme degli archi (o lati), e ogni arco collega una coppia di vertici. In parole povere: $V$ sono le scatole, $E$ sono le frecce. Useremo $|V|$ per il numero di vertici e $|E|$ per il numero di archi; quando il contesto è chiaro li abbreviamo in $V$ ed $E$ .

I grafi si classificano lungo quattro assi indipendenti.

Diretto o non diretto. In un grafo diretto ogni arco ha un verso: l’arco $u \to v$ non implica l’arco $v \to u$ . Modella relazioni asimmetriche — strade a senso unico, “il modulo A importa il modulo B”, “il task X precede il task Y”. In un grafo non diretto l’arco $\{u, v\}$ è simmetrico: modella relazioni reciproche — un’amicizia, un cavo di rete, una strada a doppio senso.

Pesato o non pesato. In un grafo pesato ogni arco porta un numero — un costo, una distanza, una latenza, una capacità, una probabilità. In un grafo non pesato gli archi esistono e basta, o equivalentemente hanno tutti peso 1.

Ciclico o aciclico. Un ciclo è un cammino che parte da un nodo e ci ritorna seguendo gli archi. Un grafo che non contiene cicli è aciclico. Un grafo diretto e aciclico è un DAG (directed acyclic graph): la sottoclasse più importante per questo capitolo e per l’AI pratica.

Connesso o disconnesso. Un grafo non diretto è connesso se da ogni nodo si raggiunge ogni altro. Se non lo è, si spezza in “isole”: le componenti connesse.

Un’ultima nozione: il grado di un nodo è il numero di archi che lo toccano. Nei grafi diretti si separa in in-degree (archi entranti) e out-degree (archi uscenti). L’in-degree avrà un ruolo da protagonista tra poco. E un caso particolare merita un nome: un albero è un grafo non diretto, connesso, aciclico, con esattamente $V-1$ archi. Ogni albero è un grafo; non ogni grafo è un albero.

Mettere un grafo in memoria

Sapere cos’è un grafo non basta: bisogna decidere come rappresentarlo come dato. Le due rappresentazioni canoniche hanno trade-off opposti, e sceglierle bene cambia le prestazioni di tutto ciò che ci gira sopra.

La matrice di adiacenza è una matrice $V \times V$ di numeri. La cella $A[i][j]$ vale 1 (o il peso dell’arco) se esiste l’arco da $i$ a $j$ , e 0 altrimenti. Per un grafo non diretto la matrice è simmetrica. Costi:

Spazio: $O(V^2)$ — si paga per ogni coppia possibile di nodi, anche quelle non collegate.
Test “esiste l’arco $(u, v)$ ?”: $O(1)$ — un singolo accesso alla cella.
Iterare i vicini di $u$ : $O(V)$ — bisogna scorrere l’intera riga $u$ e scartare gli zeri.

La lista di adiacenza è un array di $V$ liste. La lista in posizione $i$ contiene i vicini del nodo $i$ . Costi:

Spazio: $O(V + E)$ — si paga solo per i nodi e per gli archi che esistono davvero.
Test “esiste l’arco $(u, v)$ ?”: $O(\text{grado di } u)$ — bisogna scorrere la lista di $u$ .
Iterare i vicini di $u$ : $O(\text{grado di } u)$ — ottimale, si tocca solo ciò che serve.

# Stesso grafo diretto, due rappresentazioni.
# Archi: 0->1, 0->2, 1->2, 2->3

# Matrice di adiacenza: 4x4, sedici celle.
matrice = [
    [0, 1, 1, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 1],
    [0, 0, 0, 0],
]

# Lista di adiacenza: solo i quattro archi reali.
lista = {
    0: [1, 2],
    1: [2],
    2: [3],
    3: [],
}

La regola pratica è netta. Quasi tutti i grafi del mondo reale sono sparsi: $E$ è molto più piccolo di $V^2$ . Un social network con un miliardo di utenti non ha un miliardo al quadrato di amicizie; una mappa stradale non ha una strada tra ogni coppia di incroci; un grafo di dipendenze software ha pochi archi per modulo. Per i grafi sparsi la lista di adiacenza vince su entrambi i fronti: meno memoria e iterazione dei vicini più veloce. La matrice di adiacenza conviene solo per grafi densi ( $E$ vicino a $V^2$ ) o quando servono moltissimi test di adiacenza puntuali su coppie arbitrarie. Quasi tutti gli algoritmi di questo capitolo girano in $O(V + E)$ su lista di adiacenza e degradano a $O(V^2)$ su matrice.

BFS e DFS come attraversamenti

I due attraversamenti fondamentali di un grafo — visitare i nodi in modo sistematico — sono BFS e DFS. Hanno un capitolo dedicato, search-bfs-dfs, che li sviscera come algoritmi di ricerca di un nodo obiettivo. Qui interessa solo il loro ruolo come attraversamenti generali, perché sono il motore degli algoritmi che seguono.

BFS (breadth-first search, ricerca in ampiezza) esplora il grafo a ondate concentriche: prima tutti i nodi a distanza 1 dalla sorgente, poi tutti quelli a distanza 2, e così via. La sua frontiera è una coda FIFO. Su un grafo non pesato, BFS trova il cammino con il minimo numero di archi.

DFS (depth-first search, ricerca in profondità) esplora andando il più a fondo possibile lungo un cammino, e torna indietro (backtrack) solo quando si blocca. La sua frontiera è una pila LIFO, o equivalentemente la pila delle chiamate ricorsive.

Entrambi visitano ogni nodo e ogni arco una volta, quindi costano $O(V + E)$ su lista di adiacenza. Su questo scheletro si costruiscono tre operazioni ricorrenti:

Componenti connesse. Lancia un attraversamento da ogni nodo non ancora visitato. Ogni lancio scopre esattamente una componente. Costo totale $O(V + E)$ .
Rilevamento di cicli. In un grafo non diretto, incontrare durante l’attraversamento un nodo già visitato diverso dal padre segnala un ciclo. In un grafo diretto, un back edge durante DFS — un arco che punta a un nodo ancora “in corso di esplorazione” — segnala un ciclo.
Alberi di copertura. Gli archi effettivamente usati per scoprire nodi nuovi durante un attraversamento formano un albero che tocca tutti i nodi della componente: uno spanning tree. BFS produce uno spanning tree dei cammini minimi (in numero di archi); DFS produce uno spanning tree profondo e ramificato in modo diverso. Lo stesso grafo, due alberi diversi, a seconda dell’attraversamento.

DFS in particolare, classificando gli archi che incontra durante l’esplorazione, abilita una famiglia di algoritmi lineari. Gli archi si dividono in tree edge (quelli che scoprono un nodo nuovo), back edge (quelli che tornano su un antenato ancora aperto, e segnalano un ciclo), forward edge e cross edge (collegamenti verso parti già completate). È proprio da questa classificazione — e in particolare dal riconoscimento dei back edge — che nasce il primo algoritmo di ordinamento topologico.

L’ordinamento topologico

Arriviamo al cuore del capitolo. Dato un DAG, un ordinamento topologico è una sequenza lineare di tutti i suoi vertici tale che, per ogni arco $u \to v$ , il nodo $u$ compaia prima di $v$ nella sequenza. È la vestizione completa che non viola nessun vincolo dell’Angolo 2.

Due fatti vanno fissati subito. Primo: un ordinamento topologico esiste se e solo se il grafo è un DAG. Se c’è anche un solo ciclo, nessuna sequenza può soddisfare tutti i vincoli — i nodi del ciclo si pretendono a vicenda. Secondo: l’ordinamento in generale non è unico. Se calzini e maglietta non hanno vincoli reciproci, “calzini poi maglietta” e “maglietta poi calzini” sono entrambi ordinamenti validi. L’ordinamento è unico solo nel caso estremo in cui i vincoli formino una catena totale — tecnicamente, un cammino hamiltoniano che tocca ogni nodo una volta.

Ci sono due strade classiche per calcolarlo. Vale la pena vederle entrambe, perché illustrano due modi di pensare diversi.

Algoritmo di Kahn

L’algoritmo di Kahn (1962) lavora sull’in-degree, e ha il sapore di una BFS.

def kahn(grafo, vertici):
    # in_degree[v] = numero di archi entranti in v
    in_degree = {v: 0 for v in vertici}
    for u in vertici:
        for v in grafo[u]:
            in_degree[v] += 1

    # I nodi senza dipendenze entranti sono "pronti".
    pronti = [v for v in vertici if in_degree[v] == 0]
    ordine = []

    while pronti:
        u = pronti.pop()
        ordine.append(u)
        for v in grafo[u]:
            in_degree[v] -= 1          # u e' "rimosso": v perde una dipendenza
            if in_degree[v] == 0:
                pronti.append(v)

    if len(ordine) < len(vertici):
        raise ValueError("ciclo rilevato: ordinamento impossibile")
    return ordine

Riga per riga. Prima si calcola l’in-degree di ogni nodo: quante frecce gli puntano contro, cioè da quanti vincoli dipende. I nodi con in-degree 0 non dipendono da nessuno: sono i “pronti”, quelli che si possono mettere in fila subito. Si estrae un nodo pronto, lo si appende al risultato, e lo si “rimuove” idealmente dal grafo: ogni suo vicino perde una dipendenza, quindi il suo in-degree cala di uno. Quando il contatore di un vicino arriva a zero, anche quel vicino diventa pronto ed entra nella collezione. Il ciclo continua finché ci sono nodi pronti.

Il controllo finale è elegante: se il risultato non contiene tutti i $V$ nodi, alcuni nodi non hanno mai raggiunto in-degree 0. L’unica ragione possibile è che siano intrappolati in un ciclo, in cui ognuno aspetta l’altro per sempre. L’algoritmo di ordinamento è anche un rilevatore di cicli. Il costo è $O(V + E)$ : ogni nodo e ogni arco viene toccato una volta sola.

Algoritmo basato su DFS

La seconda strada, attribuita a Tarjan, sfrutta una proprietà sottile della DFS.

def toposort_dfs(grafo, vertici):
    stato = {v: "nuovo" for v in vertici}   # nuovo / in_corso / fatto
    ordine = []

    def dfs(u):
        stato[u] = "in_corso"
        for v in grafo[u]:
            if stato[v] == "in_corso":
                raise ValueError("ciclo rilevato")   # back edge
            if stato[v] == "nuovo":
                dfs(v)
        stato[u] = "fatto"
        ordine.append(u)        # post-order: u dopo tutti i suoi discendenti

    for u in vertici:
        if stato[u] == "nuovo":
            dfs(u)
    return ordine[::-1]         # si inverte la lista

L’idea è questa: durante una DFS, un nodo viene marcato “fatto” e appeso alla lista solo dopo che tutti i nodi da lui raggiungibili sono stati esplorati. Questo è il momento del post-order. Ne segue che, nella lista, ogni nodo compare dopo tutti quelli che dipendono da lui. Invertendo la lista alla fine, si ottiene l’ordine corretto: chi non dipende da nessuno finisce in testa.

Il rilevamento dei cicli usa una marcatura a tre stati. Un nodo è “nuovo” se non ancora toccato, “in_corso” se la sua DFS è iniziata ma non finita, “fatto” se completata. Incontrare un arco verso un nodo “in_corso” significa aver chiuso un anello tornando su un antenato ancora aperto: è un back edge, e quindi un ciclo.

Quale dei due

I due algoritmi hanno lo stesso costo $O(V + E)$ e producono entrambi un ordinamento valido (in generale diverso). Kahn produce l’ordine “dall’alto”, emettendo prima le sorgenti, ed è iterativo: non rischia il superamento della pila di ricorsione su grafi profondi. Se la collezione pronti diventa una coda a priorità, Kahn produce facilmente l’ordinamento topologico lessicograficamente minimo — utile quando serve un output deterministico e canonico. La variante DFS è più compatta e riusa la ricorsione, ma su un DAG molto profondo può esaurire la pila di chiamate. In pratica i build system e i package manager tendono a usare Kahn o sue varianti, proprio per il controllo dell’ordine e l’assenza di ricorsione.

Cammini minimi: il quadro completo

Trovare il cammino di costo minimo da una sorgente a tutti gli altri nodi di un grafo pesato è uno dei problemi più studiati. Due algoritmi lo risolvono in regimi diversi.

Dijkstra è trattato in dettaglio in search-a-star. Funziona su grafi con pesi degli archi non negativi. È greedy: mantiene una stima di distanza per ogni nodo, estrae ripetutamente dalla coda a priorità il nodo con distanza provvisoria minima e rilassa i suoi archi (cioè aggiorna le stime dei vicini se passare da lì conviene). Con un heap binario costa $O((V + E) \log V)$ .

Dijkstra ha però un punto cieco preciso: i pesi negativi. La sua correttezza si basa sul fatto che, una volta estratto un nodo, la sua distanza è definitiva e non va più rivista. Con un arco di peso negativo questa garanzia salta: un nodo già “chiuso” potrebbe diventare raggiungibile a costo minore attraverso un cammino più lungo che passa per l’arco negativo. Un’idea che sembra furba — “aggiungo una costante a tutti i pesi per renderli positivi” — non funziona: la costante si somma una volta per arco, quindi penalizza i cammini lunghi più di quelli corti e cambia quale cammino è il minimo.

Per i pesi negativi serve Bellman-Ford (Richard Bellman 1958, Lester Ford 1956). La sua logica è la forza bruta del rilassamento: invece di scegliere con cura quale nodo trattare, rilassa tutti gli archi del grafo, e ripete l’operazione $V-1$ volte. Il motivo del numero $V-1$ è semplice: un cammino minimo senza cicli ha al più $V-1$ archi, e ogni passata “propaga” la stima corretta di almeno un arco lungo ogni cammino. Dopo $V-1$ passate, tutte le distanze minime sono corrette.

Bellman-Ford regala anche un rilevatore di cicli negativi. Si fa una passata in più, la $V$ -esima: se qualche distanza migliora ancora, esiste un ciclo di peso complessivo negativo — e in quel caso il “cammino minimo” non è nemmeno definito, perché girare il ciclo all’infinito abbassa il costo senza limite. Il prezzo di tutta questa robustezza è il tempo: $O(V \cdot E)$ , sensibilmente più lento di Dijkstra.

def bellman_ford(vertici, archi, sorgente):
    # archi e' una lista di triple (u, v, peso)
    dist = {v: float("inf") for v in vertici}
    dist[sorgente] = 0

    for _ in range(len(vertici) - 1):       # V-1 passate
        for u, v, peso in archi:
            if dist[u] + peso < dist[v]:    # rilassamento
                dist[v] = dist[u] + peso

    for u, v, peso in archi:                # passata di verifica
        if dist[u] + peso < dist[v]:
            raise ValueError("ciclo negativo rilevato")
    return dist

Alberi di copertura minimi e union-find

Un ultimo problema classico, in forma di cenno. Dato un grafo non diretto, connesso e pesato, un minimum spanning tree (MST) è un sottoinsieme di archi che collega tutti i nodi, senza cicli, con peso totale minimo. È esattamente $V-1$ archi. Modella problemi del tipo “collega tutte queste città con il minor cavo possibile” o “raggruppa questi punti con il minor costo di unione”.

Due algoritmi greedy lo risolvono. Kruskal ordina tutti gli archi per peso crescente e li scorre, aggiungendo un arco all’albero solo se non crea un ciclo; costa $O(E \log E)$ , dominato dall’ordinamento. Prim fa crescere l’albero da un nodo iniziale, aggiungendo ogni volta l’arco più leggero che esce dall’albero corrente; con un heap costa $O(E \log V)$ , e ha un sapore molto simile a Dijkstra.

Kruskal ha bisogno di rispondere in fretta a una domanda: “questi due nodi sono già collegati dall’albero parziale?” — perché se lo sono, aggiungere un arco tra loro creerebbe un ciclo. La struttura dati che risponde è union-find (o disjoint-set, insiemi disgiunti). Mantiene una partizione di elementi in gruppi disgiunti e offre tre operazioni: make_set crea un gruppo con un solo elemento, find restituisce il rappresentante del gruppo di un elemento, union fonde due gruppi. La domanda di Kruskal diventa: find(u) == find(v)? Se i due nodi hanno lo stesso rappresentante sono già nello stesso albero, e l’arco va scartato; altrimenti l’arco si aggiunge e si fa union dei due gruppi.

Con due ottimizzazioni standard — union by rank (si attacca sempre l’albero più basso sotto quello più alto, per non farlo crescere) e path compression (durante una find, ogni nodo attraversato viene riagganciato direttamente alla radice) — ogni operazione costa tempo ammortizzato $O(\alpha(n))$ , dove $\alpha$ è l’inversa della funzione di Ackermann: una funzione che cresce così lentamente da restare sotto 5 per qualunque $n$ immaginabile. In pratica, tempo costante. Union-find non serve solo a Kruskal: è la struttura standard per tenere traccia delle componenti connesse di un grafo che cresce un arco alla volta, un problema che ricorre in clustering, in gestione di reti e nei sistemi distribuiti.

Riepilogo della complessità

Algoritmo	Tempo	Spazio	Note
BFS / DFS	$O(V + E)$	$O(V)$	su lista di adiacenza
Ordinamento topologico	$O(V + E)$	$O(V)$	Kahn o DFS
Dijkstra (con heap)	$O((V + E) \log V)$	$O(V)$	pesi $\geq 0$
Bellman-Ford	$O(V \cdot E)$	$O(V)$	tollera pesi negativi
Kruskal	$O(E \log E)$	$O(V)$	usa union-find
Prim (con heap)	$O(E \log V)$	$O(V)$	sapore Dijkstra
Union-find (per operazione)	$O(\alpha(n))$ ammortizzato	$O(n)$	quasi costante

La riga da ricordare: su lista di adiacenza, attraversamenti e ordinamento topologico sono lineari nella dimensione del grafo. Su matrice di adiacenza, BFS e DFS degradano a $O(V^2)$ , perché ogni “iterare i vicini” costa $O(V)$ .

Esempi

Esempio 1 — un grafo numerico di dipendenze

Considera cinque target di build, con queste dipendenze (l’arco $u \to v$ significa ” $v$ dipende da $u$ , quindi $u$ va compilato prima”):

config  -> libreria
config  -> cli
libreria -> cli
libreria -> test
cli     -> test

L’in-degree iniziale: config ha 0, libreria ha 1 (da config), cli ha 2 (da config e libreria), test ha 2 (da libreria e cli). C’è un quinto target, docs, senza dipendenze: in-degree 0.

Kahn parte con i nodi a in-degree 0: config e docs. Emette config, e decrementa i suoi vicini: libreria passa a 0, cli passa a 1. Ora i pronti sono docs e libreria. Emette docs (nessun vicino), poi libreria: cli passa a 0, test passa a 1. Emette cli: test passa a 0. Emette test. Ordine finale: config, docs, libreria, cli, test. Tutti e cinque i nodi sono usciti, quindi nessun ciclo. Nota che docs poteva comparire ovunque rispetto agli altri: l’ordinamento non è unico.

Esempio 2 — ordinamento topologico in codice, con rilevamento di un ciclo

grafo_valido = {
    "config": ["libreria", "cli"],
    "libreria": ["cli", "test"],
    "cli": ["test"],
    "test": [],
    "docs": [],
}
print(kahn(grafo_valido, grafo_valido.keys()))
# -> ['config', 'docs', 'libreria', 'cli', 'test']  (un ordine valido)

grafo_circolare = {
    "a": ["b"],
    "b": ["c"],
    "c": ["a"],     # dipendenza circolare
}
try:
    kahn(grafo_circolare, grafo_circolare.keys())
except ValueError as e:
    print(e)
# -> ciclo rilevato: ordinamento impossibile

Il secondo caso è esattamente l’errore che un package manager mostra quando due librerie si richiedono a vicenda. Nessun nodo del ciclo a -> b -> c -> a raggiunge mai in-degree 0, quindi pronti si svuota prima di aver emesso tutti i nodi, e il controllo finale scatta. La diagnostica “dipendenza circolare” che leggi nei log di build non è un messaggio speciale: è un ordinamento topologico che ha fallito.

Esempio 3 — un DAG di sottotask agentici

Un agente riceve l’obiettivo “aggiungi l’autenticazione all’applicazione e apri una pull request”. Decompone in sottotask con dipendenze:

leggi_codebase — nessuna dipendenza.
scrivi_modello_utente — dipende da leggi_codebase.
scrivi_endpoint_login — dipende da scrivi_modello_utente.
scrivi_test — dipende da scrivi_endpoint_login.
aggiorna_docs — dipende da scrivi_endpoint_login.
apri_pr — dipende da scrivi_test e aggiorna_docs.

Questo è un DAG. Un ordinamento topologico — per esempio leggi_codebase, scrivi_modello_utente, scrivi_endpoint_login, scrivi_test, aggiorna_docs, apri_pr — è una sequenza di esecuzione valida. Ma l’orchestratore può fare di più: i nodi che a un certo punto hanno tutti in-degree 0 contemporaneamente sono indipendenti tra loro e possono essere eseguiti in parallelo. Dopo scrivi_endpoint_login, sia scrivi_test sia aggiorna_docs diventano pronti: un agente con due worker può lanciarli insieme. È la stessa logica con cui make -j parallelizza la compilazione. Il grafo di dipendenze, una volta esplicitato, non dà solo un ordine: dà anche il massimo parallelismo possibile.

Esempio 4 — quando un peso negativo rompe Dijkstra

Un esempio piccolo ma istruttivo, per vedere dove Dijkstra sbaglia. Considera tre nodi e questi archi diretti pesati: $S \to A$ con peso 1, $S \to B$ con peso 4, $A \to B$ con peso $-3$ . Vogliamo la distanza minima da $S$ .

Dijkstra parte con $\text{dist}(S) = 0$ e tutto il resto a infinito. Estrae $S$ , rilassa: $\text{dist}(A) = 1$ , $\text{dist}(B) = 4$ . Ora estrae il nodo a distanza minima rimasto, $A$ con 1, e lo marca definitivo. Rilassa l’arco $A \to B$ : $1 + (-3) = -2$ , che è minore di 4, quindi $\text{dist}(B) = -2$ . Estrae $B$ . Risultato di Dijkstra: $\text{dist}(B) = -2$ . In questo caso, per fortuna, è corretto.

Ma sposta l’estrazione: se $B$ fosse stato estratto e marcato definitivo prima che $A$ rilassasse l’arco negativo — cosa che accade non appena la topologia è un filo più complessa — Dijkstra avrebbe chiuso $B$ a 4 e non lo avrebbe più toccato, restituendo 4 invece di $-2$ . La garanzia di Dijkstra (“il nodo estratto ha distanza definitiva”) presume che nessun arco futuro possa abbassarla, e un arco negativo viola esattamente questo. Bellman-Ford, rilassando tutti gli archi a ogni passata senza mai “chiudere” un nodo, non ha questo punto cieco: troverebbe $-2$ in ogni caso. È il prototipo del bug silenzioso descritto nella sezione “Dove si rompe”: nessun errore a runtime, solo un numero sbagliato.

Applicazioni pratiche

L’ordinamento topologico è uno di quegli algoritmi che, una volta riconosciuto, si vede ovunque.

Build system. make, Bazel, cargo, i compilatori incrementali: tutti costruiscono un grafo dei target — un file oggetto dipende dai sorgenti, un eseguibile dai file oggetto — e lo ordinano topologicamente per decidere la sequenza di compilazione. L’opzione make -j per la compilazione parallela è esattamente lo sfruttamento dei nodi indipendenti dell’Esempio 3.

Package manager. pip, npm, apt, cargo risolvono le dipendenze dei pacchetti ordinando topologicamente il grafo “A richiede B”. Installano una libreria solo dopo tutte quelle da cui dipende. Quando rilevano una dipendenza circolare, è un ordinamento topologico che ha fallito su un ciclo.

Autodiff e backpropagation. È l’applicazione che riguarda più da vicino il machine learning, e merita la sezione che segue.

Fogli di calcolo. Quando una cella contiene =A1+B1, dipende da A1 e B1. Il motore di ricalcolo costruisce il grafo delle dipendenze tra celle e lo ordina topologicamente: una cella si ricalcola solo dopo le celle da cui dipende. Il classico errore “riferimento circolare” è — di nuovo — un ciclo nel grafo.

Sistemi agentici e orchestrazione. Un agente che pianifica decompone un obiettivo in un DAG di sottotask. L’esecuzione segue un ordinamento topologico; i task sullo stesso “livello” si parallelizzano. Gli orchestratori di workflow (Airflow, Dagster, e in generale i sistemi di task scheduling) sono motori di ordinamento topologico con monitoraggio sopra.

Knowledge graph e sistemi RAG. Un knowledge graph è una rappresentazione strutturata della conoscenza come grafo: i nodi sono entità (persone, organizzazioni, concetti), gli archi sono relazioni tipate (“scritto da”, “parte di”, “precede”). I sistemi RAG di nuova generazione, come GraphRAG di Microsoft Research, costruiscono un knowledge graph dal corpus di documenti e lo affiancano alla ricerca vettoriale per il retrieval. Il vantaggio è che certe domande — tracciare una dipendenza, esplorare il vicinato di un’entità, confrontare entità collegate, fare multi-hop reasoning — diventano attraversamenti di grafo (BFS/DFS a profondità limitata), invece di richiedere l’iniezione di grandi blocchi di testo nel contesto. Il grafo gestisce la struttura, l’LLM gestisce l’interpretazione.

Vale la pena fissare la distinzione, perché è facile confonderla. La ricerca vettoriale risponde a “quali documenti somigliano alla domanda” — è geometria in uno spazio di embedding. L’attraversamento di un knowledge graph risponde a “quali entità sono collegate a questa, e come” — è la teoria dei grafi di questo capitolo. Sono due meccanismi ortogonali, e i sistemi più solidi li usano insieme: la ricerca vettoriale per trovare il punto di ingresso nel grafo, l’attraversamento per espandere il contesto lungo le relazioni rilevanti. Riconoscere che un BFS a due o tre salti sta sotto la fase di espansione di un retriever rende molto meno misteriosa l’architettura di un sistema RAG basato su grafo.

Il grafo computazionale e l’autodiff

L’esempio più importante per chi lavora con il machine learning. Quando un framework di deep learning (PyTorch, TensorFlow, JAX) esegue un modello, costruisce — esplicitamente o al volo — un grafo computazionale: un DAG in cui i nodi sono operazioni elementari (somma, prodotto matriciale, ReLU, softmax) e gli archi rappresentano il flusso dei dati da un’operazione all’altra. Gli input — il batch di dati, i parametri della rete — sono le sorgenti del DAG; la loss finale è il pozzo.

La forward pass — calcolare l’output del modello — è una valutazione del grafo in ordine topologico. Ogni nodo-operazione può essere calcolato solo quando tutti i suoi input esistono già, ed è esattamente la condizione che l’ordinamento topologico garantisce. Non è un’analogia: è letteralmente lo stesso algoritmo. Un framework che esegue una rete sta facendo un ordinamento topologico del suo grafo computazionale.

La backward pass — calcolare i gradienti per il training — percorre lo stesso grafo in ordine topologico inverso, dalla loss verso gli input. A ogni nodo si applica la regola della catena (vedi derivate-parziali-jacobiani): il nodo riceve il gradiente “a valle” e lo propaga ai suoi genitori. L’autodiff in reverse mode — il nome tecnico della backpropagation — è, meccanicamente, un ordinamento topologico inverso più la regola della catena applicata a ogni nodo. L’ordine inverso non è una scelta arbitraria: garantisce che, quando si calcola il gradiente di un nodo, i gradienti di tutti i nodi che dipendono da lui siano già stati calcolati e pronti da combinare.

Riconoscere questa identità ha un valore concreto. Spiega perché un grafo computazionale deve essere aciclico (un ciclo renderebbe sia la forward sia la backward indefinite — è la stessa ragione per cui le RNN vengono “srotolate” nel tempo prima di calcolare i gradienti). Spiega perché operazioni indipendenti nel grafo si possono fondere o parallelizzare. E spiega perché gli stessi due algoritmi da trenta righe di questo capitolo stanno sotto sia a un build system sia all’addestramento di una rete neurale.

C’è anche una ricaduta pratica sul debugging. Quando un framework segnala un errore del tipo “elemento del grafo modificato dopo essere stato usurato dalla forward, gradiente non calcolabile”, o quando un grafo computazionale costruito a mano produce gradienti None, la diagnosi quasi sempre si riduce a una violazione della struttura DAG: un nodo è stato sovrascritto, oppure un arco di dipendenza è andato perso, e l’ordinamento topologico inverso non trova più il cammino dalla loss a quel parametro. Pensare in termini di nodi, archi e ordine topologico rende leggibili messaggi di errore che altrimenti sembrano arcani.

Cenno: le graph neural network

Se il grafo non è solo la struttura su cui gira un algoritmo, ma è il dato stesso da cui si vuole imparare — una molecola, un social network, un grafo di citazioni — servono le graph neural network (GNN): reti neurali che operano direttamente su grafi. Il loro meccanismo centrale è il message passing, formalizzato da Gilmer et al. nel 2017: a ogni passo, ogni nodo calcola un messaggio per ciascun vicino, aggrega i messaggi ricevuti con una funzione invariante all’ordine (somma o media), e aggiorna il proprio stato. Iterando, l’informazione si propaga lungo gli archi e ogni nodo cattura pattern del proprio vicinato e di parti via via più lontane del grafo. È un capitolo a sé; qui basta sapere che esiste e che chiude il cerchio: dopo aver usato i grafi come strumento, si arriva a un’AI che impara dai grafi.

Dove si rompe

Gli algoritmi di questo capitolo sono solidi e ben compresi, ma hanno confini precisi. Conoscerli è importante quanto conoscere i meccanismi.

L’ordinamento topologico richiede un DAG, e i grafi reali ciclano. Il presupposto “il grafo è aciclico” è forte. Le dipendenze software diventano circolari per errore; i fogli di calcolo sviluppano riferimenti circolari; i grafi di task mal progettati contengono cicli. Quando questo accade, l’algoritmo non produce un ordine: fallisce. La buona notizia è che fallisce in modo diagnostico — rileva il ciclo. Ma il chiamante deve gestire quel fallimento, non assumere che l’ordinamento riesca sempre. Un sistema che si limita a leggere il risultato senza controllare il caso “ciclo” si comporta in modo indefinito proprio quando i dati sono più malati.

La non-unicità sorprende. Molti si aspettano che topological_sort sia una funzione deterministica come sort su una lista di numeri. Non lo è: su un DAG con nodi indipendenti, ordini diversi sono tutti corretti, e l’ordine restituito dipende dall’implementazione (l’ordine di iterazione dei vicini, la struttura della collezione pronti). Codice che si affida implicitamente a un ordine specifico — “tanto i task escono sempre così” — è fragile: cambia la struttura dati interna e l’output cambia, pur restando valido. Se serve un ordine canonico, va imposto esplicitamente (per esempio con la coda a priorità nell’algoritmo di Kahn).

Dijkstra e i pesi negativi. Vale la pena ripeterlo perché è un errore frequente: Dijkstra dà risultati silenziosamente sbagliati su grafi con archi di peso negativo. Non lancia un’eccezione, restituisce semplicemente distanze non minime. E il “trucco” di traslare tutti i pesi per renderli positivi non funziona, perché distorce il costo relativo dei cammini in base al numero di archi. Se i pesi possono essere negativi — sconti, rimborsi, energia recuperata — serve Bellman-Ford, e si paga il fattore $O(V \cdot E)$ .

La scelta della rappresentazione non è cosmetica. Usare una matrice di adiacenza su un grafo sparso grande è un errore di prestazioni serio: un grafo con un milione di nodi e dieci milioni di archi sta benissimo come lista di adiacenza, ma come matrice richiederebbe $10^{12}$ celle — terabyte di zeri. E l’iterazione dei vicini, $O(V)$ invece di $O(\text{grado})$ , può rendere un BFS lineare un BFS quadratico. La scelta sbagliata non rompe la correttezza, ma può rendere l’algoritmo inutilizzabile in pratica.

I grafi davvero grandi non stanno in memoria. Tutti gli algoritmi visti assumono che il grafo — nodi, archi e le strutture ausiliarie come visited o in_degree — stia nella RAM di una singola macchina. Per i grafi su scala web (miliardi di nodi) questo presupposto cade, e servono approcci distribuiti, streaming o out-of-core che cambiano la natura degli algoritmi. Lo stesso BFS, su un grafo che non sta in memoria, diventa un problema di sistemi distribuiti, non più un esercizio da trenta righe.

Cammino minimo non è sempre quello che serve. BFS trova il cammino con meno archi, Dijkstra quello a costo minimo, ma molti problemi reali vogliono altro: tutti i cammini, il secondo cammino migliore, un cammino che eviti certi nodi, un cammino sotto un budget e sopra una soglia. Questi sono problemi diversi, alcuni molto più difficili (trovare il cammino più lungo in un grafo generale, per esempio, è NP-hard — diventa facile solo se il grafo è un DAG). Riconoscere quale variante si ha davanti è metà del lavoro.

Cicli “buoni” e cicli “cattivi”. La parola ciclo non è di per sé negativa. In un grafo di dipendenze un ciclo è un bug; in un grafo di stati (una catena di Markov, un automa) un ciclo è normale e desiderato — lo stato può tornare dov’era. Applicare l’ordinamento topologico a un grafo che deve ciclare è un errore concettuale: lì servono altri strumenti, e una catena di Markov è proprio un grafo diretto pesato in cui i cicli sono il punto.

La rappresentazione del grafo si “sporca” nel tempo. Gli algoritmi assumono un grafo fisso, dato in input. Ma i grafi dei sistemi reali cambiano: archi che si aggiungono, nodi che spariscono, pesi che si aggiornano. Un ordinamento topologico calcolato ieri non è più valido se oggi è stata aggiunta una dipendenza. Ricalcolare tutto da zero a ogni modifica è spesso accettabile per grafi piccoli, ma su grafi grandi e in rapida evoluzione servono algoritmi incrementali o dinamici, che mantengono il risultato aggiornato senza ripartire da capo. Sono più complessi e fuori dallo scope di questo capitolo, ma vale sapere che il passaggio da grafo statico a grafo dinamico non è gratis.

I pesi non sono sempre numeri sommabili. Tutti i cammini minimi visti assumono che il costo di un cammino sia la somma dei pesi degli archi, e che “minimo” sia ben definito. Molti problemi reali hanno costi che non si sommano: la latenza peggiore lungo un cammino è un massimo, non una somma; l’affidabilità è un prodotto di probabilità; un cammino può avere vincoli multipli incomparabili (veloce ma costoso contro lento ed economico). Riconoscere quando il modello “somma di pesi” non si applica evita di usare Dijkstra dove non ha senso — anche se a volte una trasformazione algebrica riconduce il problema alla forma standard.

Collegamenti

search-bfs-dfs — i due attraversamenti che questo capitolo riassume, sviscerati come algoritmi di ricerca con frontiera, visited set, completezza e ottimalità.
search-a-star — Dijkstra e A* in dettaglio: i cammini minimi quando si ha un’euristica che orienta la ricerca.
programmazione-dinamica — Bellman-Ford è programmazione dinamica sui cammini; il cammino minimo su un DAG si risolve con DP in ordine topologico.
viterbi — il cammino più probabile in un HMM è un cammino minimo su un DAG a strati (il trellis): stesso scheletro, su un grafo costruito ad hoc.
monte-carlo-tree-search — l’albero di gioco è un grafo, e MCTS lo attraversa e lo costruisce in modo incrementale.
complessita-big-o (in preparazione) — la notazione $O(V + E)$ , $O(V^2)$ , $O(\alpha(n))$ usata per misurare tutti gli algoritmi di questo capitolo.
derivate-parziali-jacobiani — la regola della catena che la backward pass applica a ogni nodo del grafo computazionale, ordinato topologicamente.
catene-markov (in preparazione) — una catena di Markov è un grafo diretto pesato dove i pesi sono probabilità e i cicli sono il punto, non un bug.
equazione-bellman (in preparazione) — il “Bellman” dei cammini minimi e quello dell’equazione di Bellman in reinforcement learning condividono l’idea del rilassamento e della programmazione dinamica.
knowledge-graph (in preparazione) — i knowledge graph come struttura per il context engineering e i sistemi RAG basati su grafo.

Per andare oltre

Le fonti che seguono spaziano dal riferimento accademico classico alla documentazione di strumenti moderni: la teoria dei grafi è una delle aree dell’informatica con la migliore continuità tra il materiale degli anni ‘60 e la pratica di oggi.

Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (MIT Press, 4ª ed. 2022): i capitoli sui grafi elementari, l’ordinamento topologico, i cammini minimi e gli MST sono il riferimento standard, con prove complete.
Robert Tarjan, “Depth-First Search and Linear Graph Algorithms”, SIAM Journal on Computing 1(2), 1972: il paper che trasforma DFS in un framework e da cui discende l’ordinamento topologico via post-order.
Arthur B. Kahn, “Topological sorting of large networks”, Communications of the ACM 5(11), 1962: la fonte primaria dell’algoritmo basato su in-degree.
Sanchez-Lengeling et al., “A Gentle Introduction to Graph Neural Networks”, Distill, 2021 (distill.pub/2021/gnn-intro): introduzione visiva e accessibile alle reti neurali su grafi.
“GraphRAG” di Microsoft Research (microsoft.github.io/graphrag): documentazione e motivazioni dei sistemi RAG basati su knowledge graph, con il retrieval visto come attraversamento.