Matrice di Adiacenza¶

Uno dei modi più semplice per implementare un grafo è quello di usare una matrice bidimensionale. In questa matrice, ciascuna delle righe e delle colonne corrisponde a un vertice del grafo. Il valore memorizzato nella cella alla riga \(v\) e nella colonna \(w\) indica se c’è un arco tra il vertice \(v\) e il vertice \(w\). Quando due vertici sono connessi da un arco, diciamo che sono adiacenti. Figura 2 mostra la matrice di adiacenza per il grafo in Figura 1. Un valore in una cella rappresenta il peso dell’arco dal vertice \(v\) al vertice \(w\).

Figura 2: Una matrice di adiacenza

Il vantaggio è che è semplice e permette di vedere velocemente se due nodi sono connessi oppure no. Tuttavia bisogna notare che la maggioranza delle celle è vuota. Quando questo avviene diciamo che la matrice è “sparsa”. Una matrice non è il metodo più efficiente per memorizzare dati sparsi e deve essere evitata.

La matrice di adiacenza è una buona implementazione per un grafo se il numero di archi è grande. Ma cosa significa grande? Il numero di archi richiesto per riempire la matrice è \(|V|^2\). Una matrice è piena quando ogni vertice è connesso a ogni altro. Grafi di questo tipo, o comunque con \(O(|V|^2)\) archi sono rari. La maggior parte delle volte abbiamo a che fare con grafi sparsi.