Grafi

I grafi sono una struttura dati che prevede più nodi connessi tra loro. In questo senso è una estensione del concetto di albero, a sua volta estensione del concetto di lista.

Rivediamo le definizioni:

• Lista: è una struttura dati composta da nodi (ovvero entità che rappresentano unità di informazione, come valori numerici, stringhe, array, o struct) collegati uno con l’altro in sequenza, ovvero dove ogni nodo è collegato ad un altro. A seconda del tipo di lista può essere una pila, una coda, una lista concatenata.

• Albero: è una struttura dati dove c’è un nodo (detto padre) può essere collegato a più di un nodo (detto figlio), che a sua volta può essere padre di altri figli. Il nodo di partenza viene chiamato radice. I collegamenti sono chiamati archi (detti anche rami). Come si vede la lista è un caso speciale di albero (con un figlio solo).

Definiamo ora due concetti:

• un percorso è una sequenza arbitraria di nodi collegati che tra loro che permette di andare da un nodo iniziale ed uno finale.
• un cammino è un percorso che non attraversa mai più di 1 volta lo stesso nodo.

Possiamo facilmente vedere che un albero (e quindi anche una lista) ha sempre uno ed un solo cammino tra due nodi qualsiasi.

Il grafo estende questo concetto: è una struttura dati composta da nodi ed archi dove esiste più di un cammino tra due nodi qualsiasi. Come si può vedere in figura, la struttura a sinistra è un albero, la struttura a destra aggiunge un arco e rende possibili più cammini alternativi per connettere due nodi.

Un grafo quindi consente di avere una strutturazione dell’informazione non legata ad una gerarchia, ma a connessioni tra informazioni che permettono di gestire relazioni logiche e semantiche “tra pari”.

I grafi possono avere archi direzionali, come in figura, che vengono chiamati grafi orientati.

Nella figura, il grafo a sinistra è orientato ciclico (DCG) perchè esiste almeno un cammino che permette di tornare al punto di partenza. Il grafo a sinistra è orientato aciclico (DAG) perché nessun cammino consente di tornare al punto di partenza.

Quando usare gli alberi e quando usare i grafi

Gli alberi sono legati quindi a modelli di informazione dove si vogliono rappresentare dati legati da una classificazione o una gerarchia, ed imporre quindi tra loro relazioni rigide. Un grafo invece è più adatto a quei modelli informativi dove non solo non è prevista una relazione gerarchica, ma esistono molteplici modi per collegare le singole entità, attraverso cammini differenti.

Gli alberi quindi sono usati per:

• descrivere documenti;
• creare organigrammi
• definire modelli di classificazione;
• organizzare l’informazione in modo ordinato.

Ad esempio sono alberi i documenti HTML, gli organigrammi aziendali, i filesystem, gli alberi binari di ricerca (per ordinare numeri), la struttura dei router di una rete.

I grafi sono invece usati per:

• definire strutture dove collegare tra loro idee o concetti;
• realizzare mappe che definiscono cammini e percorsi possibili tra entità;
• organizzare l’informazione senza porre vincoli gerarchici

Ad esempio sono grafi le mappe concettuali, i modelli di reti stradali, la struttura della rete Internet, i siti del Word Wide Web.

Per capire nel concreto proviamo ad ipotizzare una struttura concettuale per gestire il collegamento tra queste entità: Docente, Classe, Materia, Studente. Con un albero potremmo ipotizzare questa struttura:

Per quanto efficace a gestire il legame tra docenti, materie e studenti ad una classe, questa struttura è limitata sia perché definisce implicitamente una gerarchia sia perché non permette di esplicitare la relazione diretta che c’è tra un docente ed una materia.

Il grafo può rappresentare meglio questa informazione aggiungendo un collegamento diretto:

In questo caso la mappa si può leggere in due modi:

• come una relazione che lega la classe ai concetti di studente, materia e docente;
• come una relazione tra docente, materia e classe, che a sua volta è collegata allo studente.

I grafi sono usati anche come strumento per lo sviluppo di applicazioni, mediante:

• diagrammi di flusso (permettono di definire sequenze di istruzioni, condizioni e cicli);
• automi a stati finiti (permettono di gestire nodi-stato, e archi-cambiamenti di stato).

In figura un esempio di grafo che rappresenta gli stati possibili di un processo di un sistema operativo.

Nodi, archi, densità e peso

Se indichiamo con N il numero di nodi, ed A come il numero di archi possiamo definire la densità come il rapporto tra il numero di archi presenti ed il numero massimo di archi possibili:

La densità minima si misura se ogni nodo è collegato ad un altro con un solo arco, quindi sono presenti N-1 archi. La densità minima è quindi pari a:

Il numero massimo di archi si ha quando ogni nodo è collegato con qualsiasi altro nodo. Dati N nodi ci sono quindi N-1 archi. Siccome però gli archi sono reciproci, andrà dimezzato il valore totale Ovvero N=2 ci sarà 1 arco, N=3 avrà 3 archi, N=4 avrà 6 archi, N=5 avrà 10 archi, e così via.

In totale si avranno quindi questi archi:

La densità massima è quindi 1.

Gli archi inoltre possono essere “pesati”, ovvero possiamo associare ad ogni arco un valore numerico, detto “peso”. I grafi pesati sono estremamente utili quando si vuole modellare strutture dati per rappresentare ad esempio reti di calcolatori (il peso indica il tempo che ci impiega un pacchetto che va da un nodo ad un altro) o mappe stradali (il peso indica la distanza), come anche in modelli scientifici ed economici.

Grafi in C++

Vi sono due modi classici per rappresentare un grafo in C/C++.
Il primo metodo è tramite l’utilizzo di liste di adiacenza. Ad ogni nodo del grafo viene associata una lista concatenata che contiene tutti i nodi adiacenti (cioè collegati direttamente con esso). Questo metodo tuttavia occupa molta memoria e non è molto efficiente, e lo si usa solo quando la densità è molto bassa.

L’altro metodo è invece tramite l’utilizzo di una matrice.

Vediamo il codice:

#include <iostream>
using namespace std;

struct node {
    int pos;
    char name;
};

bool** createGraph(int vertices) {
    bool** graph = new bool*[vertices];
    for (int i=0; i<vertices; i++) {
        graph[i] = new bool[vertices];
        for (int j=0; j<vertices; j++) {
            graph[i][j] = false;
        }
    }
    return graph;
}

void connect(bool** graph, int src, int dest) {
    graph[src][dest] = true;
    graph[dest][src] = true;
}

void print(bool** graph, int vertices) {
    for (int i=0; i<vertices; i++) {
        for (int j=0; j<vertices; j++) {
            cout << (graph[i][j] ? "*" : "-") << " ";
        }
        cout << endl;
    }
    cout << endl;
}

int main()
{
    node a = {0,'A'};
    node b = {1,'B'};
    node c = {2,'C'};
    bool** graph = createGraph(3);
    connect(graph, 0, 1);
    connect(graph, 0, 2);
    print(graph, 3);
    

    return 0;
}

Il metodo createGraph crea una tabella di bool che connette coppie di nodi.

In pratica creiamo un elenco di nodi con indicata una posizione ciascuno nella matrice.

Il metodo connect semplicemente mette a true la connessione tra il nodo in posizione src e il nodo in posizione dst.

In questo esempio abbiamo visto un grafo non orientato e non pesato.

La versione orientata prevede collegamenti asimmetrici e la versione pesata non usa un tipo booleano, ma da un valore al peso dell’arco. La loro implementazione è lasciata per esercizio.