Table of Contents
Grafi
Grafi e rappresentazioni
I grafi sono strutture dati caratterizzate dalla presenza di vertici e archi e sono solitamente rappresentati da G(V, E), in cui G è il grafico, V è l'insieme dei vertici e E - senza troppa fantasia - l'insieme degli archi.
I grafi solitamente sono rappresentati o da matrici o da liste. Se sono rappresentati da matrici, la memoria utilizzata è Θ(V2), perché ogni possibile arco è rappresentato, e il valore all'incrocio tra i due vertici è 1 se l'arco esiste, 0 altrimenti.
| V1 | V2 | V3 | V4 | V5 | |
|---|---|---|---|---|---|
| V1 | 0 | 1 | 1 | 0 | 0 |
| V2 | 1 | 1 | 0 | 0 | 0 |
| V3 | 1 | 0 | 0 | 1 | 1 |
| V4 | 0 | 0 | 1 | 0 | 0 |
| V5 | 0 | 0 | 1 | 0 | 0 |
In questo esempio i vertici sono (V1, V2, V3, V4, V5) e gli archi sono ((V1, V2), (V2, V2), (V1, V3), (V3, V4), (V3, V5)).
Se il grafo è semplice, la matrice deve essere trasponibile senza che il risultato cambi; in altre parole, l'informazione di un "triangolo" di dati pari a V*(V-1)/2 è ridondante, perché l'arco (V1, V2) e (V2, V1) sono la stessa cosa:
| V1 | V2 | V3 | V4 | V5 | |
|---|---|---|---|---|---|
| V1 | 0 | 1 | 1 | 0 | 0 |
| V2 | 1 | 1 | 0 | 0 | |
| V3 | 1 | 0 | 0 | 1 | 1 |
| V4 | 0 | 0 | 1 | 0 | 0 |
| V5 | 0 | 0 | 1 | 0 | 0 |
Se invece gli archi hanno una direzione - come ad esempio le strade a senso unico, che vanno da V1 a V2 ma non viceversa - tutti gli archi sono importanti perché rappresentano un'informazione univoca.
La rappresentazione tramite liste di adiacenza invece contengono una lista di vertici, a ciascuno dei quali corrisponde una lista di altri vertici a cui sono collegati.
Il grafo riportato sopra sarebbe:
- V1 → V2 → V3
- V2 → V1 → V2
- V3 → V1 → V4 → V5
- V4 → V3
- V5 → V3
Anche in questo caso, se il grafo non è orientato, alcune informazioni sono ridondanti (es. il collegamento tra V1 e V2 è rappresentato sia nella lista V1 sia nella V2), mentre nel caso di grafi orientati i due collegamenti rappresenterebbero entità diverse e non ci sarebbe ridondanza.
Visita del grafo
La visita del grafo permette, partendo da un vertice, di "toccare" tutti gli altri vertici collegati direttamente o indirettamente.
Si comincia da una sorgente, come nel problema dei flussi di Ricerca Operativa, e si visitano tutti i nodi collegati. Per fare questo, si colorano i nodi dapprima di bianco, poi in grigio, se sono stati visitati, e in nero se tutti i nodi adiacenti sono a loro volta stati visitati (sono in grigio o in nero).
Il seguito nel post Visita di un grafo.