UN lista di adiacenze è una struttura dati utilizzata per rappresentare un grafico in cui ciascun nodo nel grafico memorizza un elenco dei suoi vertici vicini.

Rappresentazione grafica del grafico diretto alla lista di adiacenze

fai while loop java

Caratteristiche della lista di adiacenza:

• La dimensione della matrice è determinata dal numero di nodi nella rete.
• Il numero di archi del grafico è facilmente calcolabile.
• L'elenco delle adiacenze è a matrice frastagliata .

Come costruire una lista di adiacenze?

È molto facile e semplice costruire un elenco di adiacenze per un grafico; di seguito sono riportati alcuni passaggi che è necessario seguire:

• Crea una serie di elenchi collegati di dimensioni N , dove N è il numero di vertici nel grafico.
• Crea un elenco collegato di vertici adiacenti per ciascun vertice nel grafico.
• Per ogni bordo (tu, v) nel grafico, aggiungi In all'elenco collegato di In , e aggiungi In all'elenco collegato di In se il grafico non è orientato altrimenti aggiungere In all'elenco di In se è diretto da In A In . (In caso di grafici pesati memorizzare il peso insieme alle connessioni).

Applicazioni della lista di adiacenza:

• Algoritmo di Dijkstra , Prima ricerca in ampiezza , E Prima ricerca in profondità utilizzare elenchi di adiacenza per rappresentare i grafici.
• Elaborazione delle immagini : Gli elenchi di adiacenza possono essere utilizzati per rappresentare le relazioni di adiacenza tra i pixel in un'immagine.
• Sviluppo del gioco : questi elenchi possono essere utilizzati per memorizzare informazioni sulle connessioni tra diverse aree o livelli. Gli sviluppatori di giochi utilizzano i grafici per rappresentare mappe o livelli di gioco.

Vantaggi dell'utilizzo di un elenco di adiacenze:

• Un elenco di adiacenze è semplice e facile da capire.
• Aggiungere o rimuovere bordi da un grafico è semplice e veloce.

Svantaggi dell'utilizzo di un elenco di adiacenze:

• Nelle liste di adiacenza l'accesso ai bordi può richiedere più tempo rispetto alla matrice di adiacenza.
• Richiede più memoria della matrice di adiacenza per i grafi densi.

Cos'altro puoi leggere?

• Significato e definizione della matrice di adiacenza nei DSA
• Aggiungi e rimuovi bordo nella rappresentazione dell'elenco di adiacenze di un grafico
• Converti la matrice di adiacenza nella rappresentazione dell'elenco di adiacenza del grafico
• Convertire la lista di adiacenza nella rappresentazione della matrice di adiacenza di un grafico
• Confronto tra la rappresentazione della lista di adiacenza e della matrice di adiacenza del grafico