Grafi e algoritmi di ricerca

Come visitare un grafo e trovare cammini di peso minimo

Gli alberi permettono di rappresentare solo relazioni strettamente gerarchiche (dove ogni nodo ha un unico padre e non esistono cicli). Quando dobbiamo modellare relazioni arbitrarie tra coppie di oggetti — come una rete stradale di città, la topologia dei router di Internet, le amicizie in un social network, o le dipendenze tra pacchetti software — utilizziamo la struttura matematica e informatica più generale: il Grafo.


Definizione formale e terminologia dei Grafi

Un Grafo è una coppia ordinata dove:

  • è un insieme finito e non vuoto di elementi chiamati vertici (o nodi); indichiamo il numero di vertici con .
  • è un insieme di coppie di vertici chiamate archi (o spigoli / lati, edges); indichiamo il numero di archi con .

Classificazione dei grafi

  1. Grafo Non Orientato (Undirected Graph):
    Gli archi sono coppie non ordinate : la connessione è bidirezionale/simmetrica ( equivale a , come l’amicizia reciproca o una strada a doppio senso). Il numero massimo di archi (senza cappi) è .
  2. Grafo Orientato o Digrafo (Directed Graph):
    Gli archi sono coppie ordinate rappresentate da frecce , dove è la coda/sorgente e è la testa/destinazione (come i link tra pagine web o il “seguire” su un social). Il numero massimo di archi è .
  3. Grafo Pesato (Weighted Graph):
    Ad ogni arco è associato un numero reale chiamato peso o costo (es. distanza in km, latenza in ms, costo del pedaggio).
flowchart LR
    subgraph NonOrientato["Grafo Non Orientato"]
        U0((0)) --- U1((1))
        U0 --- U2((2))
        U1 --- U2
        U2 --- U3((3))
    end
    subgraph OrientatoPesato["Grafo Orientato e Pesato (Digrafo)"]
        D0((0)) -->|"peso 4"| D1((1))
        D0 -->|"peso 2"| D2((2))
        D2 -->|"peso 1"| D1
        D1 -->|"peso 5"| D3((3))
    end

Grado, Cammini, Cicli, Connessione e Alberi

  • Adiacenza e Grado: Se , il vertice si dice adiacente a .

    • In un grafo non orientato, il grado è il numero di archi incidenti in . Vale il Lemma delle strette di mano: .
    • In un grafo orientato, si distinguono il grado entrante () (numero di frecce che arrivano in ) e il grado uscente () (numero di frecce che partono da ). Vale .
  • Cammino (Path): Una sequenza di vertici collegati da archi consecutivi . La lunghezza del cammino è il numero di archi (o la somma dei pesi in un grafo pesato). Un cammino è semplice se non ripete vertici.

  • Ciclo (Cycle): Un cammino di lunghezza in cui il vertice finale coincide con quello iniziale (). Un grafo privo di cicli si dice aciclico. Un grafo orientato aciclico è chiamato DAG (Directed Acyclic Graph).

  • Connessione e Alberi Liberi: Un grafo non orientato è connesso se esiste almeno un cammino tra qualsiasi coppia di vertici. Un Albero è semplicemente un grafo non orientato connesso e aciclico, ed è caratterizzato dalla relazione fondamentale:

  • Grafo Sparso vs Grafo Denso: Un grafo si dice sparso se (es. , come le reti stradali dove ogni incrocio ha strade); si dice denso se .


Rappresentazione dei Grafi in memoria in C

Supponendo di numerare i vertici da a , esistono due strutture dati canoniche per rappresentare un grafo:

1. Matrice di Adiacenza (Adjacency Matrix)

È una matrice quadrata di dimensione in cui:

(Nota: se il grafo non è orientato, la matrice di adiacenza è simmetrica: ).

2. Liste di Adiacenza (Adjacency Lists)

È un array di puntatori a liste concatenate, dove la lista adj[u] contiene esclusivamente i vertici adiacenti a (cioè gli archi uscenti da ).

flowchart LR
    subgraph AdjList["Rappresentazione con Liste di Adiacenza"]
        A0["adj[0]"] --> L01["1 | ●"] --> L02["2 | NULL"]
        A1["adj[1]"] --> L13["3 | NULL"]
        A2["adj[2]"] --> L21["1 | ●"] --> L23["3 | NULL"]
        A3["adj[3]"] --> L3N["NULL"]
    end

Tabella comparativa: Matrice vs Liste di Adiacenza

Criterio / OperazioneMatrice di AdiacenzaListe di Adiacenza
Spazio di memoria **$\Theta(V
Testare se esiste l’arco (basta leggere A[u][v]) (bisogna scorrere la lista adj[u])
Scorrere tutti i vicini di **$\Theta(V
Inserire un arco (inserimento in testa a adj[u])
Quando conviene usarla?Grafi DENSI ($E

Algoritmi di Visita e Ricerca sui Grafi

Per esplorare tutti i vertici raggiungibili da un vertice sorgente senza cadere in cicli infiniti, manteniamo un array booleano visitato[V] (inizializzato a 0). Esistono due strategie universali di esplorazione, entrambe di complessità ottima con liste di adiacenza (e con matrice di adiacenza):

La BFS esplora il grafo “a onde concentriche” (per livelli di distanza dalla sorgente ): prima visita (distanza ), poi tutti i vicini a distanza , poi tutti i vertici a distanza , e così via.

  • Struttura dati di supporto: utilizza una Coda FIFO (Queue).
  • Proprietà fondamentale: In ogni grafo non pesato, la BFS calcola la distanza minima dist[v] (cammino minimo col minor numero di archi) dalla sorgente a tutti gli altri vertici, costruendo l’albero dei cammini minimi tramite il vettore dei padri padre[v]!

La DFS esplora il grafo spingendosi il più lontano possibile lungo un singolo cammino finché non incontra un vicolo cieco (tutti i vicini già visitati), per poi fare backtracking all’ultimo bivio non ancora esaurito.

  • Struttura dati di supporto: utilizza la ricorsione (lo Stack delle chiamate) oppure una Pila LIFO (Stack) esplicita.
  • Applicazioni: Individuazione di cicli, calcolo delle componenti connesse, ordinamento topologico di un DAG, risoluzione di labirinti.

Cenni all’Algoritmo di Dijkstra per Grafi Pesati ()

Quando gli archi hanno pesi positivi diversi tra loro, il cammino con meno archi (trovato dalla BFS) non è necessariamente il cammino di peso totale minimo!
L’Algoritmo di Dijkstra generalizza la BFS sostituendo la Coda FIFO con una Coda con Priorità (Min-Heap):

  1. Inizializza dist[s] = 0 e dist[v] = +INFINITO per tutti gli altri vertici;

  2. Ad ogni passo estrae il vertice non ancora definitivo avente dist[u] minima;

  3. Rilassa (Relaxation) tutti gli archi uscenti : se passare per migliora la distanza verso , aggiorna:


Implementazione completa in C: Grafo con Liste di Adiacenza, BFS e DFS

#include <stdio.h>
#include <stdlib.h>
 
/* Nodo di una lista di adiacenza */
typedef struct ArcoNodo {
    int dest;
    struct ArcoNodo *next;
} ArcoNodo;
 
/* Struttura del Grafo con Liste di Adiacenza */
typedef struct {
    int V;            /* Numero di vertici (0 .. V-1) */
    ArcoNodo **adj;   /* Array di V puntatori alle liste di adiacenza */
} Grafo;
 
Grafo *grafo_crea(int V) {
    Grafo *g = (Grafo *)malloc(sizeof(Grafo));
    if (!g) return NULL;
    g->V = V;
    g->adj = (ArcoNodo **)calloc(V, sizeof(ArcoNodo *));
    if (!g->adj) { free(g); return NULL; }
    return g;
}
 
/* Aggiunge un arco orientato u -> v in tempo O(1) */
void grafo_aggiungi_arco(Grafo *g, int u, int v) {
    ArcoNodo *nuovo = (ArcoNodo *)malloc(sizeof(ArcoNodo));
    if (!nuovo) return;
    nuovo->dest = v;
    nuovo->next = g->adj[u];
    g->adj[u] = nuovo;
}
 
/* === 1. VISITA IN AMPIEZZA (BFS) con calcolo delle distanze minime === */
void grafo_bfs(const Grafo *g, int sorgente) {
    int *visitato = (int *)calloc(g->V, sizeof(int));
    int *dist     = (int *)malloc(g->V * sizeof(int));
    int *coda     = (int *)malloc(g->V * sizeof(int));
    int head = 0, tail = 0;
 
    for (int i = 0; i < g->V; i++) dist[i] = -1;
 
    /* Inizializza la BFS dalla sorgente */
    visitato[sorgente] = 1;
    dist[sorgente] = 0;
    coda[tail++] = sorgente; /* enqueue(sorgente) */
 
    printf("Ordine BFS da %d: ", sorgente);
    while (head < tail) {
        int u = coda[head++]; /* dequeue() */
        printf("%d(d=%d) ", u, dist[u]);
 
        /* Esplora tutti i vicini v di u */
        for (ArcoNodo *p = g->adj[u]; p != NULL; p = p->next) {
            int v = p->dest;
            if (!visitato[v]) {
                visitato[v] = 1;
                dist[v] = dist[u] + 1;
                coda[tail++] = v; /* enqueue(v) */
            }
        }
    }
    printf("\n");
    free(visitato);
    free(dist);
    free(coda);
}
 
/* === 2. VISITA IN PROFONDITA (DFS) ricorsiva === */
static void dfs_ric(const Grafo *g, int u, int visitato[]) {
    visitato[u] = 1;
    printf("%d ", u);
 
    for (ArcoNodo *p = g->adj[u]; p != NULL; p = p->next) {
        int v = p->dest;
        if (!visitato[v]) {
            dfs_ric(g, v, visitato);
        }
    }
}
 
void grafo_dfs(const Grafo *g, int sorgente) {
    int *visitato = (int *)calloc(g->V, sizeof(int));
    printf("Ordine DFS da %d: ", sorgente);
    dfs_ric(g, sorgente, visitato);
    printf("\n");
    free(visitato);
}
 
void grafo_distruggi(Grafo *g) {
    if (!g) return;
    for (int i = 0; i < g->V; i++) {
        ArcoNodo *curr = g->adj[i];
        while (curr) {
            ArcoNodo *succ = curr->next;
            free(curr);
            curr = succ;
        }
    }
    free(g->adj);
    free(g);
}

Cammini minimi con Dijkstra e Bellman–Ford

Il rilassamento di un arco orientato u → v di peso w aggiorna d[v] e il predecessore se d[u] è finita e d[u] + w < d[v]. Con rappresentazioni intere, teniamo lo stato irraggiungibile separato e verifichiamo che la somma sia rappresentabile prima di calcolarla. La lista di adiacenza permette di visitare solo gli archi uscenti.

Dijkstra con pesi non negativi

Consideriamo S → A (4), S → B (1), B → A (2), A → T (1) e B → T (6). Estraendo S si ottengono d[A]=4 e d[B]=1. Estraendo B si aggiornano d[A]=3 e d[T]=7. Estraendo A si migliora d[T] a 4, quindi si estrae T. Seguendo i predecessori otteniamo S → B → A → T. La distanza minima temporanea diventa definitiva all’estrazione: proseguire da un altro vertice ancora da elaborare non può ridurla con archi di peso non negativo. Ci fermiamo quando il prossimo minimo è infinito o non ci sono candidati. Con selezione del minimo per scansione e matrice, il tempo è . Con liste e min-heap indicizzato è per .

Bellman–Ford e cicli negativi

Bellman–Ford scorre tutti gli archi per al più passate, rilassando solo quelli con coda raggiungibile. Si può terminare presto se nessun valore cambia. Senza cicli negativi raggiungibili, un cammino minimo può essere scelto semplice e usa al più archi. Dopo passate sono state considerate almeno tutte le possibilità con al più archi. Il costo con una lista di archi è e la memoria ausiliaria è .

Esempio. In ogni passata consideriamo gli archi nell’ordine A → T (2), B → A (-3), S → B (5) e S → A (4).

Passatad[S]d[A]d[B]d[T]
00
1045
20256
30254

La distanza di T è 4 via S → B → A → T. Per rilevare cicli negativi raggiungibili, dopo le passate controlliamo se un altro rilassamento può migliorare una distanza. Aggiungendo A → B (2), il ciclo B → A → B pesa ed è raggiungibile da S. Una passata ulteriore trova ancora un miglioramento. I vertici raggiungibili da quel ciclo non hanno distanza minima finita. Un ciclo che la sorgente non raggiunge non influenza le sue distanze.


Esempi guidati

Esempio 1: Traccia passo-passo di BFS e DFS su un grafo concreto

Dato il grafo non orientato con e liste di adiacenza (ordinate in senso crescente):

  • adj[0] = {1, 2}
  • adj[1] = {0, 3, 4}
  • adj[2] = {0, 4}
  • adj[3] = {1, 5}
  • adj[4] = {1, 2, 5}
  • adj[5] = {3, 4}
  1. Traccia della BFS partendo da 0:

    • Livello : Coda [0] estrae 0, scopre e accoda i vicini 1 () e 2 (). Coda: [1, 2].
    • Livello :
      • Estrae 1, scopre e accoda 3 () e 4 (). Coda: [2, 3, 4].
      • Estrae 2, i suoi vicini 0 e 4 sono già visitati! Coda: [3, 4].
    • Livello :
      • Estrae 3, scopre e accoda 5 (). Coda: [4, 5].
      • Estrae 4, i suoi vicini 1, 2, 5 sono già visitati! Coda: [5].
    • Livello : Estrae 5. Coda vuota.
    • Sequenza BFS: 0, 1, 2, 3, 4, 5.
  2. Traccia della DFS ricorsiva partendo da 0:

    • Visita 0 scende nel primo vicino non visitato 1 scende nel primo vicino 3 scende in 5 scende in 4 scende in 2. Da 2 tutti i vicini (0 e 4) sono già visitati, quindi risale fino a 0.
    • Sequenza DFS: 0, 1, 3, 5, 4, 2.

Esempio 2: Contare il numero di Componenti Connesse di un grafo non orientato

Se un grafo non è connesso, è formato da più “isole” disgiunte chiamate componenti connesse. Per contarle in tempo , basta eseguire un ciclo su tutti i vertici : ogni volta che troviamo un vertice non ancora visitato, incrementiamo il contatore delle isole e lanciamo una DFS/BFS da che marcherà tutta la sua isola!

int conta_componenti_connesse(const Grafo *g) {
    int *visitato = (int *)calloc(g->V, sizeof(int));
    int num_componenti = 0;
 
    for (int v = 0; v < g->V; v++) {
        if (!visitato[v]) {
            num_componenti++; /* Trovata una nuova componente connessa! */
            dfs_ric(g, v, visitato); /* Marca tutti i vertici raggiungibili da v */
        }
    }
    free(visitato);
    return num_componenti;
}

Errori frequenti

Errori da evitare

  1. Dimenticare l’array visitato[] durante la visita di un grafo:
    A differenza degli alberi (che non hanno cicli), i grafi possono contenere cicli (o archi bidirezionali ). Senza il vettore visitato[], sia la BFS sia la DFS rimbalzano all’infinito tra e fino al crash!
  2. Nella BFS, marcare visitato[v] = 1 solo quando v viene estratto dalla coda (dequeue) anziché quando viene inserito (enqueue):
    Se si marca un vertice come visitato solo al momento della dequeue, lo stesso vertice v può essere accodato più volte da più vicini diversi prima di essere estratto, gonfiando la coda e rallentando l’algoritmo. Regola d’oro: visitato[v] = 1 va impostato subito prima di enqueue(v)!
  3. Applicare l’algoritmo di Dijkstra a grafi con archi di peso negativo:
    Dijkstra assume che aggiungere un arco a un cammino non possa mai diminuirne il peso totale (). Con pesi negativi, rendere definitiva la distanza all’estrazione può dare un risultato errato. Bellman–Ford tratta anche questi archi.

Esercizi di prova

Esercizio 1. Scelta tra Matrice e Liste di Adiacenza (Base)

Un grafo orientato rappresenta una rete stradale con incroci e tratti stradali. Calcola l’ordine di grandezza della memoria richiesta dalla Matrice di Adiacenza (assumendo 1 byte per cella) rispetto alle Liste di Adiacenza, e stabilisci quale rappresentazione è necessaria.

Esercizio 2. Calcolo di grado entrante e uscente su Matrice di Adiacenza (Base)

Dato un grafo orientato rappresentato tramite una matrice di adiacenza int A[V][V], scrivi due funzioni int grado_uscente(int A[V][V], int u) e int grado_entrante(int A[V][V], int u) e indicane la complessità temporale.

Esercizio 3. Verifica di grafo non orientato tramite simmetria (Intermedio)

Scrivi una funzione int matrice_simmetrica(int V, int A[V][V]) che verifica se la matrice di adiacenza A rappresenta un grafo non orientato privo di cappi ( e ) ispezionando solo il triangolo superiore della matrice.

Esercizio 4. Ricostruzione del cammino minimo dopo la BFS (Intermedio)

Supponi che la BFS a partire da sorgente abbia popolato il vettore dei padri int padre[V] (dove padre[sorgente] = -1 e padre[v] = u indica che v è stato scoperto da u). Scrivi una procedura ricorsiva void stampa_cammino(const int padre[], int s, int dest) che stampa i vertici del cammino minimo da s a dest nell’ordine corretto da s a dest.

Esercizio 5. Test se un grafo non orientato è un Albero (Avanzato)

Ricordando che un grafo non orientato è un albero se e solo se è connesso e ha esattamente archi, spiega come verificare in tempo se un grafo non orientato rappresentato con liste di adiacenza è un albero.

Esercizio 6. Traccia dell’Algoritmo di Dijkstra (Avanzato)

Dato un grafo orientato pesato con vertici e archi:
, , , , ,
calcola passo dopo passo il vettore delle distanze minime dist[] dalla sorgente 0 applicando l’algoritmo di Dijkstra.


Provenienza del materiale

  • Dispensa ufficiale del corso: C1PROG1U6L4_Ricerca_Applicata_ai_Grafi.pdf (Unità 6, Lezione 4 — Ricerca applicata ai grafi).
  • Marco Anisetti, Algoritmi e strutture dati dinamiche, C1PROG1_Appunti_di_fine_unità_6.pdf, capp. 2 e 4.