|
|
L’idea è quella di mantenere esplicitamente gli insiemi di adiacenza per ogni nodo del grafo. Due metodi per fare questo sono:
Liste di adiacenza, simili alle liste di trabocco viste per l’hashing
Vettori di adiacenza
Di seguito la rappresentazione grafica di grafi rappresentati con liste di adiacenza.
Supponendo di non dover inserire né cancellare nodi, si possono usare i vettori. Si suppone di avere due vettori nodi e archi; nodi ha n+1 posizioni, le prime per gli n nodi, l’ultima come sentinella. Nodi[i] contiene un cursore alla posizione di archi a partire dal quale è memorizzato A(i), dove A e l’ insieme delle adiacenze. Sia per le liste e vettori di adiacenza lo spazio di memoria occupato è O(n + m).
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.