24 – Alberi e Grafi

Oggi vediamo un pò di teoria su come creare delle strutture di dati complesse che prendono il nome di Alberi e Grafi utilizzando dei nodi.
Su come, quando o perchè usare queste strutture date lo accennerò a fine articolo ma vedremo esempi concreti di codice più avanti.

ALBERI
Rappresenta una struttura dati in cui, nella versione più semplice e generale, ciascun nodo punta ad uno o più nodi, detti figli, ed è a sua volta puntato da un solo nodo, detto padre, tranne il nodo radice che non è puntato da nessun nodo. I nodi che non hanno figli e si trovano in fondo all’albero prendono invece il nome di foglie.
Possiamo rappresentare graficamente un albero nel seguente modo:

24.1
Come possiamo notare dall’immagine ciascun nodo può avere un numero di figli maggiori o uguali a 0 mentre può avere un sono padre, eccezione fatta per il nodo radice che sta in cima a tutti.
Possiamo ovviamente realizzare alberi più “sofisticati” se necessario dove ad esempio ciascun nodo ha un terzo puntatore al proprio padre.

Alberi Binari
Costituiscono un particolare tipo di alberi in cui ciascun nodo può avere al massimo 2 figli.
Un’esempio di albero binario:

24.2
Attraverso il codice possiamo implementare un albero in maniera molto semplice attraverso le seguenti due classi:

public class Nodo {
    Nodo figliodestro;
    Nodo figliosinistro;
    int dato;
}
public class Albero{
    Nodo n;
    //METODI PER LA GESTIONE DELL'ALBERO
}

GRAFI
Rappresenta la struttura dati più complessa che possiamo costruire attraverso l’uso di nodi. In un grafo ciascun nodo può puntare ad uno o più nodi ed essere a sua volta puntato da più nodi.
Graficamente risulta chiaro cosa intendiamo per grafo (immaginiamo che ciascun nodo sia puntato e punti a sua volta al nodo a cui è collegato attraverso l’arco):

24.3
Gestire un grafo risulta molto più difficile rispetto ad una lista o ad un albero perché al contrario delle di liste e alberi il grafo non ha un nodo di “testa” o “radice” che mi permette sicuramente di raggiungere tutti gli altri.
Occorre quindi che io salva tutti i nodi del mio grafo. Un modo consiste nel creare una lista con tutti i nodi del mio grafo e per ciascun nodo creare un’altra lista con tutti i nodi che lui punta.
Volendo salvare il grafo nell’immagina sopra costruiremmo con questo metodo una struttura del genere:

24.4
Basterà quindi tenere salvato il nodo in cima con il numero 1 per poter avere accesso a tutti i nodi del nostro grafo.
Matrice di Incidenza
Un altro modo di rappresentare i vari collegamenti tra i nodi di un grafo è attraverso una matrice di incidenza. Possiamo tenere salvati tutti i nostri nodi sempre attraverso una lista ma anzichè creare un’altra lista per ciascun nodo in cui salvare i nodi a cui punta costruiamo una matrice come segue:
-la matrice sarà nxn dove n è il numero di nodi del grafo
-per ciascuna riga se il numero della riga punta al numero della colonna scrivero 1, altrimenti 0
Nel caso del grafo di prima costruiremmo la seguente matrice delle incidenze:

24.5
Nel nostro caso abbiamo una matrice simmetrica dato che nel grafo abbiamo immaginato che ciascun arco sia dotato di doppia freccia, ma è solo un eccezione!

A cosa servono?
ALBERI=queste strutture dati vengono usati in programmazione per la creazione di algoritmi di ordinamento e ricerca.
GRAFI=vengono spesso usati in dei programmi che si occupano di risolvere una classe di problemi detti “problema del percorso minimo”. Ad esempio i navigatori delle auto utilizzano dei grafi per trovare la distanza minima tra due città dove le città sono rappresentate dai nodi e le strade dagli archi.

Finisce qui questo articolo. Ho deciso di non trattare l’argomento riguardante gli algoritmi di ordinamento, sia per le liste che per alberi, sia perché sarebbe un argomento un pò lungo (e forse noioso) sia perchè su internet ci sono molti siti che ne parlano piuttosto bene. Tuttavia se volete che dedichi un articolo a qualche algoritmo di ordinamento in particolare basta che me lo chiedete nei commenti e lo faccio volentieri altrimenti dal prossimo articolo in poi inizierò a parlare di come realizzare programmi grafici in Java.
Alla prossima!

Please follow and like us: