ADT grafo

ADT grafo

L’ADT grafo è una struttura dati complessa e dinamica, viene di solito implementata come ADT di prima categoria. Il grafo viene utilizzato in tutti quei casi in cui bisogna inter-relazionare tra di loro diversi nodi o elementi, non con un solo altro nodo ma anche con più di uno, creando così dei legami tra i nodi che possono essere orientati e quindi con uno specifico verso di percorrenza o non orientati e quindi ogni legame (che viene chiamato arco) può essere percorso in entrambi i versi di percorrenza.
Gli archi in un grafo oltre a poter avere una caratteristica di orientamento, di verso, possono presentare un peso, inteso come valore numerico, anche indicato come costo per la percorrenza dell’arco cui è riferito. I grafi con archi pesati sono un sottoinsieme dello spazio di tutti i grafi.
La rappresentazione degli archi del grafo può essere fatta in due differenti modi in base alla struttura del grafo stesso:

• Lista di adiacenza: la lista di adiacenza è un vettore dinamico di puntatori ai primi nodi di n liste (n è il numero di vertici o nodi del grafo); per ogni vertice viene quindi creata una lista contenente tutti i vertici raggiungibili da quello di riferimento (nel caso di archi pesati ogni nodo della lista contiene anche il peso di quell’arco).
• Matrice di adiacenza: la matrice di adiacenza è una matrice allocata dinamicamente di dimensione NxN (N è il numero dei vertici del grafo) con ogni cella indicante se esiste il collegamento tra quel vertice ed un altro, se gli archi non sono pesati 1 per arco esistente e 0 per non esistente, se gli archi sono pesati 0 per arco non esistente e il peso dell’arco se esistente.