06 - Grafi: rappresentazione e visita (BFS/DFS)

Una rete di collegamenti, un sistema di dipendenze fra compiti, una mappa di strade: sono tutti grafi, e davanti a ciascuno ti fai le stesse due domande. Come lo scrivo in memoria, e come lo percorro senza girare in tondo per sempre? Questo articolo risponde con due rappresentazioni (lista di adiacenza e matrice) e due visite (in ampiezza, BFS, e in profondità, DFS), e le usa per risolvere quattro problemi concreti: distanza in archi, componenti connesse, ordine di esecuzione e rilevamento di cicli. Ogni algoritmo è implementato, eseguito e confrontato con networkx; la complessità è dichiarata accanto a un conteggio di operazioni, mai a un tempo. Presuppone la coda deque dell'articolo 4; gli alberi visti nell'articolo 5 sono il caso particolare di un grafo senza cicli.

Che cos'è un grafo e come lo scrivi in memoria

Un grafo è un insieme di vertici e un insieme di archi, ognuno dei quali collega due vertici. Gli archi possono essere non orientati (la strada fra due città si percorre nei due sensi) oppure orientati (un compito dipende da un altro, non viceversa). Il grado di un vertice è il numero di archi che lo toccano. Chiamo V il numero di vertici ed E il numero di archi: tutte le complessità di questo articolo si scrivono in V ed E.

La scelta di memoria è fra due strutture. La lista di adiacenza tiene, per ogni vertice, la lista dei suoi vicini; la matrice di adiacenza tiene una tabella V per V con un 1 dove l'arco esiste. Il listato costruisce entrambe su grafi casuali con V = 1.000 e densità crescente, e misura due cose: quante celle o voci occupano e quanti passi costa la domanda «esiste l'arco fra u e v?» sulla lista.

import random

def costruisci(n, archi):
    lista = [[] for _ in range(n)]
    matrice = [[0] * n for _ in range(n)]
    for u, v in archi:
        lista[u].append(v)
        lista[v].append(u)
        matrice[u][v] = matrice[v][u] = 1
    return lista, matrice

def ha_arco_lista(lista, u, v):
    passi = 0
    for w in lista[u]:  # scorre i vicini di u finche' non trova v
        passi += 1
        if w == v:
            return True, passi
    return False, passi

rng = random.Random(5)
print("V     E        celle matrice  voci liste  passi medi ha_arco(lista)")
for n, per_vertice in ((1000, 3), (1000, 50), (1000, 250)):
    archi = set()
    while len(archi) < n * per_vertice // 2:
        u, v = rng.sample(range(n), 2)
        archi.add((min(u, v), max(u, v)))
    lista, matrice = costruisci(n, sorted(archi))
    voci = sum(len(x) for x in lista)
    passi = sum(ha_arco_lista(lista, *rng.sample(range(n), 2))[1] for _ in range(5000)) / 5000
    print(f"{n:<5} {len(archi):<8} {n * n:<14} {voci:<11} {passi:.1f}")

# Output:
# V     E        celle matrice  voci liste  passi medi ha_arco(lista)
# 1000  1500     1000000        3000        3.0
# 1000  25000    1000000        50000       48.9
# 1000  125000   1000000        250000      218.4

La matrice occupa 1.000.000 di celle in tutti e tre i casi, anche con 1.500 archi veri: il suo costo dipende solo da V al quadrato. La lista occupa 3.000, 50.000 e 250.000 voci, due per arco in un grafo non orientato, quindi segue E. In cambio la lista risponde alla domanda sull'arco scorrendo i vicini: 3,0, 48,9 e 218,4 passi medi su 5.000 coppie casuali (la risposta è quasi sempre «no», quindi scorre tutta la lista), mentre la matrice risponde con una lettura. La pagina sui grafi di Algorithms, 4th edition sceglie la lista come rappresentazione predefinita; il motivo si legge nella tabella: i grafi reali sono quasi sempre radi, con E molto più piccolo di V al quadrato.

Regola pratica che ne segue: usa la lista di adiacenza quando percorri il grafo (BFS, DFS, la maggior parte degli algoritmi di questa serie), perché scorrere i vicini di un vertice costa il suo grado e non V. Usa la matrice quando il grafo è denso o quando la domanda dominante è «c'è l'arco?», o quando V è piccolo, come negli algoritmi su tutte le coppie dell'articolo 7.

BFS: visita per livelli e distanza in archi

La visita in ampiezza parte da un vertice sorgente s, visita tutti i vicini a distanza 1, poi quelli a distanza 2, e così via, usando una coda: i vertici entrano in ordine di scoperta ed escono nello stesso ordine. Il risultato è che il primo cammino con cui BFS raggiunge un vertice è un cammino con il minimo numero di archi. Pensa a un'onda in uno stagno: raggiunge prima i punti vicini e poi quelli lontani, e non torna mai indietro.

Il codice è nel modulo graph.py, che serve anche agli esempi dopo. bfs registra in dist chi è già stato visto e a che distanza; il controllo if v not in dist è la riga che impedisce di girare in tondo in un grafo con cicli: toglila e una rete con un triangolo non termina mai. parent memorizza da chi si è scoperto ciascun vertice, e cammino lo risale all'indietro per ricostruire il percorso. deque è la coda giusta perché popleft costa O(1), mentre list.pop(0) sposterebbe tutti gli elementi ogni volta, come ricorda la documentazione di deque.

from collections import deque

def bfs(adj, s):
    """Distanza in numero di archi da s; ritorna anche i genitori e gli archi esaminati."""
    dist, parent = {s: 0}, {s: None}
    coda, esaminati = deque([s]), 0
    while coda:
        u = coda.popleft()
        for v in adj[u]:
            esaminati += 1
            if v not in dist:  # il test "gia' visto" e' cio' che evita i cicli infiniti
                dist[v] = dist[u] + 1
                parent[v] = u
                coda.append(v)
    return dist, parent, esaminati

def cammino(parent, v):
    out = []
    while v is not None:
        out.append(v)
        v = parent[v]
    return out[::-1]

def dfs_ricorsiva(adj, s, visti=None, ordine=None):
    visti = set() if visti is None else visti
    ordine = [] if ordine is None else ordine
    visti.add(s)
    for v in adj[s]:
        if v not in visti:
            dfs_ricorsiva(adj, v, visti, ordine)
    ordine.append(s)  # post-order: s si chiude dopo tutti i suoi discendenti
    return ordine

def dfs_iterativa(adj, s):
    visti, ordine = {s}, []
    pila = [(s, iter(adj[s]))]
    while pila:
        u, it = pila[-1]
        for v in it:
            if v not in visti:
                visti.add(v)
                pila.append((v, iter(adj[v])))
                break
        else:  # nessun vicino nuovo: u e' concluso
            ordine.append(u)
            pila.pop()
    return ordine

def componenti(adj):
    visti, quante = set(), 0
    for s in range(len(adj)):
        if s not in visti:
            quante += 1
            visti.update(bfs(adj, s)[0])
    return quante

Un esempio piccolo mostra l'uscita. Sei stazioni, sei collegamenti a due sensi; la distanza è in archi e il percorso si ricostruisce dai genitori. Nota l'ultima riga: gli archi esaminati sono 12, cioè la somma dei gradi, perché in un grafo non orientato ogni arco compare due volte, una per ciascun estremo.

from graph import bfs, cammino

# Una rete di sei stazioni; ogni coppia e' un collegamento in entrambi i sensi
nomi = ["Lecce", "Brindisi", "Taranto", "Bari", "Foggia", "Potenza"]
archi = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5)]
adj = [[] for _ in nomi]
for u, v in archi:
    adj[u].append(v)
    adj[v].append(u)

dist, parent, esaminati = bfs(adj, 0)
for v in range(len(nomi)):
    print(nomi[v], dist[v], "->".join(nomi[x] for x in cammino(parent, v)))
print("archi esaminati:", esaminati, "= somma dei gradi:", sum(len(x) for x in adj))

# Output:
# Lecce 0 Lecce
# Brindisi 1 Lecce->Brindisi
# Taranto 1 Lecce->Taranto
# Bari 2 Lecce->Brindisi->Bari
# Foggia 3 Lecce->Brindisi->Bari->Foggia
# Potenza 4 Lecce->Brindisi->Bari->Foggia->Potenza
# archi esaminati: 12 = somma dei gradi: 12

Bari si raggiunge in 2 archi sia passando da Brindisi sia da Taranto, e BFS tiene il primo cammino che scopre, quello per Brindisi. Quando esistono più cammini minimi, quale venga restituito dipende dall'ordine delle liste di adiacenza, non dall'algoritmo.

Prova di correttezza e conteggio dei passi

Per verificare BFS e le componenti uso networkx (versione 3.7, installata in un ambiente virtuale di prova con pip install networkx), che qui è solo il riferimento indipendente: il resto dell'articolo non lo usa. Il listato genera 3.000 grafi casuali, con isolati e componenti separate, e controlla tre cose: le distanze uguali a single_source_shortest_path_length, il numero di archi esaminati uguale alla somma dei gradi dei vertici raggiunti, e il numero di componenti uguale a number_connected_components. Poi misura gli archi esaminati su tre grafi più grandi.

import random
import networkx as nx
from graph import bfs, dfs_ricorsiva, dfs_iterativa, componenti

rng = random.Random(1234)
for prova in range(3000):
    n = rng.randint(1, 25)
    m = rng.randint(0, n * 2)
    G = nx.Graph()
    G.add_nodes_from(range(n))
    for _ in range(m):
        u, v = rng.randrange(n), rng.randrange(n)
        if u != v:
            G.add_edge(u, v)
    adj = [list(G[u]) for u in range(n)]
    s = rng.randrange(n)
    dist, parent, esaminati = bfs(adj, s)
    ref = nx.single_source_shortest_path_length(G, s)
    assert dist == ref
    assert esaminati == sum(len(adj[u]) for u in dist)
    assert set(dfs_iterativa(adj, s)) == set(dist) == set(dfs_ricorsiva(adj, s))
    assert componenti(adj) == nx.number_connected_components(G)
print("3000 grafi casuali: distanze, raggiungibilita' e componenti uguali a networkx", nx.__version__)

print("V      E       archi esaminati  V+2E")
for n, e in ((1000, 3000), (10000, 30000), (100000, 300000)):
    G = nx.gnm_random_graph(n, e, seed=1)
    adj = [list(G[u]) for u in range(n)]
    dist, _, esaminati = bfs(adj, 0)
    print(f"{n:<6} {e:<7} {esaminati:<16} {n + 2 * e}  (raggiunti {len(dist)})")

# Output:
# 3000 grafi casuali: distanze, raggiungibilita' e componenti uguali a networkx 3.7
# V      E       archi esaminati  V+2E
# 1000   3000    6000             7000  (raggiunti 1000)
# 10000  30000   59998            70000  (raggiunti 9974)
# 100000 300000  600000           700000  (raggiunti 99733)

Il conteggio conferma la complessità O(V + E) dichiarata dalla pagina di Sedgewick e Wayne, che scrive «BFS takes time proportional to V + E in the worst case». Gli archi esaminati sono 2E esatti quando il grafo è connesso (6.000 su 1.000 vertici e 3.000 archi), e un po' meno quando alcuni vertici non sono raggiungibili (59.998 contro 60.000, perché 26 vertici sono isolati o in componenti separate). Il termine V si paga in altro lavoro, che qui non conto: inizializzare e leggere i vertici. Se vuoi lo stesso numero per un'altra struttura, il metodo è questo: un contatore dentro il ciclo più interno, e un confronto fra il contatore e la formula.

DFS: scendere fino in fondo, poi tornare

La visita in profondità segue un cammino finché può, e solo quando un vertice non ha più vicini nuovi torna indietro di un passo. Il percorso è quello di chi esplora un labirinto tenendo una mano sul muro. Ha una versione ricorsiva naturale, dove lo stack delle chiamate fa da memoria, e una iterativa con uno stack esplicito. Tutte e due sono in graph.py: dfs_ricorsiva e dfs_iterativa, e restituiscono l'ordine di chiusura (post-order), cioè il momento in cui un vertice non ha più nulla da esplorare.

La versione ricorsiva ha un limite che in Python si vede subito: la profondità. Su un grafo a catena di 5.000 vertici la ricorsione sfora il limite dell'interprete, che per impostazione predefinita è 1.000 e serve a evitare l'overflow dello stack C (sys.setrecursionlimit). Alzare il limite è una pezza: sposta il crash più in là, o lo trasforma in un arresto del processo. La versione iterativa tiene lo stack nella memoria dell'heap e non ha quel tetto.

from graph import dfs_ricorsiva, dfs_iterativa

n = 5000
catena = [[i + 1] if i + 1 < n else [] for i in range(n)]  # 0 -> 1 -> ... -> 4999
try:
    dfs_ricorsiva(catena, 0)
except RecursionError as e:
    print("ricorsiva:", type(e).__name__ + ":", e)
print("iterativa: visitati", len(dfs_iterativa(catena, 0)), "vertici")

# Output:
# ricorsiva: RecursionError: maximum recursion depth exceeded
# iterativa: visitati 5000 vertici

L'errore è RecursionError, un'eccezione e non un arresto, quindi lo intercetti e lo mostri; la versione iterativa visita tutti i 5.000 vertici. In dfs_iterativa lo stack contiene coppie (vertice, iteratore sui suoi vicini): il ciclo for v in it riprende da dove si era fermato, e il ramo else del for scatta solo quando l'iteratore è esaurito, cioè quando il vertice si chiude. Come per BFS, la stessa pagina dà il costo: DFS marca i vertici raggiungibili in tempo proporzionale alla somma dei loro gradi.

Ordine di esecuzione e cicli con la DFS

Un problema pratico di DFS: dati dei compiti che dipendono l'uno dall'altro, in che ordine li eseguo? Se la dipendenza è un arco da «compito» a «ciò che gli serve prima», l'ordine cercato (ordinamento topologico) esiste solo se non ci sono cicli. DFS risolve i due problemi insieme. Ogni vertice ha tre stati: bianco (mai visto), grigio (aperto, cioè sullo stack) e nero (chiuso). Un arco che arriva a un vertice grigio chiude un ciclo; se non si trova nessun arco del genere, l'ordine di chiusura, rovesciato, mette ogni compito prima di quelli che lo richiedono.

import random
import networkx as nx

BIANCO, GRIGIO, NERO = 0, 1, 2

def ordina(adj):
    """Ordine topologico per DFS, oppure un ciclo (lista di vertici) se esiste."""
    colore = [BIANCO] * len(adj)
    chiusura = []
    for radice in range(len(adj)):
        if colore[radice] != BIANCO:
            continue
        colore[radice] = GRIGIO
        pila = [(radice, iter(adj[radice]))]
        cammino = [radice]
        while pila:
            u, it = pila[-1]
            for v in it:
                if colore[v] == GRIGIO:  # arco verso un vertice ancora aperto: ciclo
                    return None, cammino[cammino.index(v):] + [v]
                if colore[v] == BIANCO:
                    colore[v] = GRIGIO
                    pila.append((v, iter(adj[v])))
                    cammino.append(v)
                    break
            else:
                colore[u] = NERO
                chiusura.append(u)
                pila.pop()
                cammino.pop()
    return chiusura[::-1], None

# arco "a -> b": a dipende da b, quindi b va eseguito prima
compiti = {"compila": ["collega"], "scarica": ["compila"], "test": ["compila"], "rilascia": ["test", "collega"], "collega": []}
nomi = list(compiti)
idx = {n: i for i, n in enumerate(nomi)}
adj = [[idx[d] for d in compiti[n]] for n in nomi]
ordine, ciclo = ordina(adj)
print("ordine di esecuzione:", [nomi[i] for i in reversed(ordine)])
adj[idx["collega"]].append(idx["rilascia"])  # dipendenza circolare
ordine, ciclo = ordina(adj)
print("ciclo:", [nomi[i] for i in ciclo])

rng = random.Random(77)
cicli = 0
for prova in range(3000):
    n = rng.randint(1, 15)
    G = nx.DiGraph()
    G.add_nodes_from(range(n))
    for _ in range(rng.randint(0, n * 2)):
        u, v = rng.randrange(n), rng.randrange(n)
        if u != v:
            G.add_edge(u, v)
    adj = [list(G.successors(u)) for u in range(n)]
    ordine, ciclo = ordina(adj)
    assert (ordine is not None) == nx.is_directed_acyclic_graph(G)
    if ordine is not None:
        pos = {v: i for i, v in enumerate(ordine)}
        assert sorted(pos) == list(range(n))
        assert all(pos[u] < pos[v] for u, v in G.edges)
    else:
        cicli += 1
        assert all(G.has_edge(a, b) for a, b in zip(ciclo, ciclo[1:])) and ciclo[0] == ciclo[-1]
print("3000 digrafi: aciclicita' concorde con networkx;", cicli, "con ciclo, ciascuno verificato arco per arco")

# Output:
# ordine di esecuzione: ['collega', 'compila', 'scarica', 'test', 'rilascia']
# ciclo: ['compila', 'collega', 'rilascia', 'test', 'compila']
# 3000 digrafi: aciclicita' concorde con networkx; 1128 con ciclo, ciascuno verificato arco per arco

Il primo esempio, cinque compiti di un rilascio, produce un ordine in cui collega precede compila, e rilascia è l'ultimo: ogni dipendenza è rispettata. Il secondo aggiunge la dipendenza circolare collega verso rilascia, e la funzione restituisce il ciclo, compila, collega, rilascia, test, compila, invece di un ordine impossibile. La prova su 3.000 grafi orientati casuali concorda con networkx.is_directed_acyclic_graph in ogni caso, e per i 1.128 grafi con ciclo il ciclo restituito è stato controllato arco per arco; per gli altri l'ordine rispetta tutti gli archi.

Perché l'arco verso un grigio è davvero un ciclo? Un vertice grigio è sullo stack, quindi è un antenato del vertice corrente nel cammino di esplorazione: l'arco chiude il percorso dall'antenato a sé stesso. Perché invece un arco verso un nero non lo è? Quel vertice è già concluso, tutto ciò che raggiunge è già stato esplorato senza tornare indietro. La distinzione grigio/nero è il punto sottile, e nel caso non orientato si semplifica, perché lì basta non contare come ciclo l'arco da cui sei appena arrivato.

Dove BFS non basta: il controesempio dei pesi

BFS minimizza il numero di archi, non il costo. Se gli archi hanno pesi, il percorso con meno archi può essere il più caro. Il listato ne costruisce uno minimo: quattro vertici, un arco diretto A-D da 10 e un percorso A-B-C-D da tre archi da 1.

from graph import bfs, cammino

# A-D diretto costa 10; A-B-C-D costa 1+1+1
archi = [("A", "D", 10), ("A", "B", 1), ("B", "C", 1), ("C", "D", 1)]
nomi = ["A", "B", "C", "D"]
ix = {n: i for i, n in enumerate(nomi)}
adj = [[] for _ in nomi]
peso = {}
for u, v, w in archi:
    adj[ix[u]].append(ix[v])
    adj[ix[v]].append(ix[u])
    peso[(ix[u], ix[v])] = peso[(ix[v], ix[u])] = w

def costo(p):
    return sum(peso[(a, b)] for a, b in zip(p, p[1:]))

dist, parent, _ = bfs(adj, ix["A"])
p = cammino(parent, ix["D"])
print("BFS: archi", dist[ix["D"]], "percorso", [nomi[i] for i in p], "costo", costo(p))
alt = [ix[x] for x in "ABCD"]
print("alternativa: archi", len(alt) - 1, "percorso", [nomi[i] for i in alt], "costo", costo(alt))

# Output:
# BFS: archi 1 percorso ['A', 'D'] costo 10
# alternativa: archi 3 percorso ['A', 'B', 'C', 'D'] costo 3

BFS sceglie il collegamento diretto, 1 arco e costo 10; il percorso da tre archi costa 3. Con pesi uniformi, o con tutti i pesi uguali a 1, le due misure coincidono e BFS è sufficiente; appena i pesi differiscono serve un altro algoritmo. Quale, e fino a quando funziona, è l'argomento dell'articolo 7.

Che cosa non c'è qui, e come scegliere fra BFS e DFS

Componenti fortemente connesse e ponti non sono trattati in questo articolo: richiedono la DFS con i tempi di scoperta e un'analisi più lunga, che Tarjan ha introdotto in Depth-First Search and Linear Graph Algorithms (SIAM Journal on Computing, 1972; ne ho letto i metadati, non il testo). La scelta fra le due visite segue la domanda.

• Distanza minima in archi da una sorgente: BFS, perché esplora per livelli.
• Esistenza di un ciclo, ordine di esecuzione, chiusura dei sottoproblemi: DFS, perché distingue i vertici aperti dai chiusi.
• Componenti connesse: indifferente, entrambe costano V + E; BFS evita il limite di ricorsione senza fatica.

La differenza pratica sta nella memoria: BFS tiene in coda un intero livello, che in un grafo molto ramificato può arrivare a essere una frazione grande dei vertici; DFS tiene sullo stack solo il cammino corrente, che può essere lungo quanto V solo in un grafo a catena, come quello del listato di ricorsione.

Che cosa sai fare adesso

Sai scegliere fra lista e matrice leggendo la densità del grafo e la domanda dominante, e sai scrivere BFS e DFS senza ricorsione che si spezzi su grafi profondi. Sai contare gli archi esaminati e confrontarli con V + E, sai ordinare compiti con dipendenze e restituire il ciclo quando l'ordine non esiste, e sai costruire un controesempio che mostra dove BFS smette di bastare. Il successivo articolo sui cammini minimi riparte da quel controesempio; prima di lui, l'articolo sugli alberi mostra le stesse visite su una struttura senza cicli.

Nella stessa serie trovi anche la complessità e Big-O, gli algoritmi di ordinamento, la ricerca lineare, binaria e con tabelle hash e il riepilogo sulla programmazione dinamica.