Concetti Chiave
- L'ADT grafo è una struttura dinamica utilizzata per interrelazionare nodi attraverso legami orientati o non orientati.
- Gli archi di un grafo possono avere un orientamento e un peso, rappresentando il costo per la percorrenza dell'arco.
- I grafi con archi pesati sono un sottoinsieme all'interno dello spazio di tutti i grafi.
- La lista di adiacenza rappresenta i vertici raggiungibili da ciascun nodo tramite puntatori, inclusi i pesi degli archi.
- La matrice di adiacenza è una matrice NxN che indica l'esistenza di collegamenti tra i vertici, usando valori 1, 0 o il peso degli archi.
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.
Caratteristiche degli archi
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.
Domande da interrogazione
- Qual è la principale funzione di un grafo nell'interrelazione tra nodi?
- Quali sono le caratteristiche degli archi in un grafo?
- Quali sono i due modi principali per rappresentare gli archi di un grafo?
Un grafo è utilizzato per inter-relazionare diversi nodi o elementi, creando legami che possono essere orientati o non orientati, permettendo così percorsi in una o entrambe le direzioni (come indicato nel testo).
Gli archi possono avere un orientamento e un peso, che rappresenta un valore numerico o costo per la percorrenza dell'arco. I grafi con archi pesati costituiscono un sottoinsieme di tutti i grafi (come descritto nel testo).
Gli archi di un grafo possono essere rappresentati tramite una lista di adiacenza, che utilizza un vettore dinamico di puntatori, o tramite una matrice di adiacenza, che è una matrice NxN che indica l'esistenza di collegamenti tra i vertici (come spiegato nel testo).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
