10 : Allocazione dinamica della memoria Vers . 8.3 – Ottobre 2023
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