Python Set per visitare grafi e rilevare cicli

Introduzione

Un set in Python è una struttura dati progettata per contenere elementi unici e verificare rapidamente se un valore appartiene a una collezione. Oltre ai casi classici, come l’eliminazione dei duplicati o il confronto tra gruppi di dati, i set sono particolarmente utili negli algoritmi di visita di grafi e alberi.

Quando si esplora una rete di pagine web, una cartella con collegamenti simbolici o una mappa di dipendenze tra moduli, è necessario ricordare quali nodi sono già stati visitati. Senza questa informazione, il programma potrebbe elaborare più volte gli stessi nodi o entrare in un ciclo infinito. Un set è ideale per questo compito perché l’operazione di appartenenza, eseguita con l’operatore in, è normalmente molto efficiente.

In questo tutorial costruiremo un esempio completo di visita di un grafo usando una ricerca in profondità, chiamata anche Depth-First Search o DFS. Useremo un set per memorizzare i nodi già elaborati e per individuare eventuali cicli.

Codice completo

from collections import defaultdict


def visita_grafo(grafo, nodo_iniziale):
    """Visita tutti i nodi raggiungibili con una DFS."""

    visitati = set()
    ordine_visita = []

    def dfs(nodo):
        # Se il nodo è già stato analizzato, non lo elaboriamo di nuovo
        if nodo in visitati:
            return

        # Registriamo il nodo nel set e nell´elenco dell´ordine
        visitati.add(nodo)
        ordine_visita.append(nodo)

        # Visitiamo ricorsivamente i nodi collegati
        for vicino in grafo[nodo]:
            dfs(vicino)

    dfs(nodo_iniziale)
    return ordine_visita, visitati


def trova_cicli(grafo):
    """Restituisce True se il grafo contiene almeno un ciclo."""

    visitati = set()
    percorso_corrente = set()

    def dfs(nodo):
        # Un nodo già nel percorso corrente indica un ciclo
        if nodo in percorso_corrente:
            return True

        # Se è già stato completato, non serve analizzarlo ancora
        if nodo in visitati:
            return False

        percorso_corrente.add(nodo)

        for vicino in grafo[nodo]:
            if dfs(vicino):
                return True

        # Il nodo non fa più parte del percorso attivo
        percorso_corrente.remove(nodo)
        visitati.add(nodo)

        return False

    for nodo in grafo:
        if dfs(nodo):
            return True

    return False


# Grafo rappresentato come dizionario di adiacenza
grafo = defaultdict(list, {
    "Python": ["Tipi", "Set"],
    "Tipi": ["Variabili"],
    "Set": ["Operazioni"],
    "Operazioni": [],
    "Variabili": ["Set"]
})

ordine, visitati = visita_grafo(grafo, "Python")

print("Ordine di visita:", ordine)
print("Nodi visitati:", visitati)
print("Il grafo contiene un ciclo:", trova_cicli(grafo))


# Aggiungiamo un collegamento che crea un ciclo:
# Variabili -

Spiegazione

Memorizzare i nodi visitati

La funzione visita_grafo crea il set vuoto visitati. Ogni volta che la funzione ricorsiva incontra un nodo, esegue:

if nodo in visitati:
    return

visitati.add(nodo)

Il primo controllo impedisce di elaborare nuovamente un nodo. Questa situazione è comune quando più percorsi portano allo stesso elemento. Il metodo add() inserisce il valore nel set; se il valore fosse già presente, il set rimarrebbe invariato.

La lista ordine_visita ha uno scopo diverso: conserva l’ordine in cui i nodi sono stati incontrati. Il set, infatti, non dovrebbe essere usato quando l’ordine degli elementi è importante. In questo esempio utilizziamo entrambe le strutture, assegnando a ciascuna un compito preciso.

Rilevare un ciclo con due set

La funzione trova_cicli utilizza due set:

• visitati: contiene i nodi già completati;
• percorso_corrente: contiene i nodi presenti nel percorso di ricorsione attualmente attivo.

La differenza è importante. Un nodo già presente in visitati è stato analizzato completamente e non rappresenta necessariamente un problema. Un nodo trovato in percorso_corrente, invece, indica che siamo tornati a un elemento ancora presente nella catena di chiamate: questo è il segnale di un ciclo.

Per esempio, se il percorso attivo è Python -> Set -> Operazioni e da Operazioni si torna a Python, il controllo:

if nodo in percorso_corrente:
    return True

interrompe la ricerca e segnala la presenza del ciclo.

Perché un set è adatto

Con una lista, per controllare se un nodo è già presente sarebbe necessario scorrere potenzialmente tutti gli elementi. Un set è invece implementato internamente tramite una tabella hash e offre, nella maggior parte dei casi, controlli di appartenenza molto rapidi. Questo vantaggio diventa significativo quando il grafo contiene migliaia o milioni di nodi.

Best practice

• Usa un set per lo stato di appartenenza, non per conservare l’ordine degli elementi.
• Scegli nomi espliciti come visitati e percorso_corrente, così il ruolo di ogni struttura è immediatamente comprensibile.
• Non modificare un set mentre lo stai attraversando con un ciclo for. Se devi farlo, lavora su una copia oppure raccogli prima le modifiche.
• Ricorda che gli elementi di un set devono essere hashable: stringhe, numeri e tuple immutabili sono adatti, mentre liste e dizionari non possono essere inseriti direttamente.
• Per grafi molto profondi, valuta una visita iterativa con una lista usata come pila, evitando il limite della ricorsione di Python.
• Se il grafo può contenere nodi isolati, analizza tutti i nodi del dizionario, non soltanto quelli raggiungibili dal nodo iniziale.

Riepilogo

I set sono strumenti fondamentali per costruire algoritmi di visita efficienti. In un grafo, il set dei nodi visitati evita elaborazioni duplicate, mentre un secondo set può rappresentare il percorso attivo e consentire di rilevare cicli.

La tecnica è applicabile a molti problemi reali: controllo delle dipendenze tra pacchetti, esplorazione di collegamenti tra pagine, gestione di reti, analisi di workflow e individuazione di riferimenti circolari. Il principio generale è semplice: usa il set per rappresentare in modo rapido lo stato di appartenenza e affiancalo a una lista o a un dizionario quando servono ordine o informazioni aggiuntive.

Approfondisci con risorse ufficiali

Per approfondire la struttura dati set, consulta la documentazione ufficiale di Python:

• Set e frozenset: https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset
• Strutture dati: https://docs.python.org/3/tutorial/datastructures.html
• Funzioni integrate e operatori: https://docs.python.org/3/library/functions.html