10: Allocazione dinamica della memoria Vers. 9.1 – Ottobre 2025
STRUTTURE DATI ASTRATTE NON LINEARI
Le strutture dati astratte lineari viste finora( lista, pila e coda) sono caratterizzate dal fatto che ogni nodo ha un solo successore( tranne l’ ultimo nodo) ed un solo predecessore( tranne il primo). Da qui deriva l’ aggettivo LINEARE.
Vogliamo estendere questi concetti a strutture dati non lineari chiamate grafi ed in particolare agli alberi che costituiscono le più importanti strutture della nuova classe di strutture da esaminare. In particolare anticipiamo che nei grafi per ogni nodo è possibile avare più nodi predecessori e più nodi successori mentre per gli alberi per ogni nodo è possibile avere più successori ma un solo predecessore( tranne il primo).
Da qui deriva l’ aggettivo NON LINEARE.
I GRAFI
DEF. Un grafo G è definito da:
- un insieme finito e non vuoto N di nodi detti anche“ vertici” o“ punti”;- un insieme A di archi detti anche“ segmenti” o“ spigoli” o“ lati”;- una funzione F che descrive le connessioni tra le coppie di nodi ossia la“ motivazione” per la quale ad ogni arco fa corrispondere una coppia di nodi.
Grafo G di esempio
A
F
C G
B E
L
I
Notazione: nodi del grafo G: arco che congiunge i nodi A e B:
D H
A, B, C, D, E, F, G, H, I, L( A, B) oppure A, B
DEF. Un nodo di un grafo G si dice DI ORDINE PARI se è collegato da un numero pari di archi, altrimenti si dice di ORDINE DISPARI.
Ad esempio nel nostro grafo G: i nodi B, I, G sono di ORDINE PARI( esattamente ordine 4) mentre i nodi A, L sono di ORDINE DISPARI( esattamente ordine 1)
DEF. Due nodi di un grafo G si dicono ADIACENTI se esiste un arco che li congiunge( altrimenti si dicono non adiacenti).
Ad esempio nel nostro grafo G: I nodi A e B sono ADIACENTI mentre i nodi A e C NON SONO ADIACENTI
Autore: Rio Chierego( email: riochierego @ libero. it- sito web: www. riochierego. it) Pag. 42