Adjacency Elenca l'elenco dell'elenco collegato o può essere rappresentato in altri modi?

-1

Sono nuovo nel grafico della struttura dei dati. Ovunque su google si dice che sia lista (o array) dell'elenco collegato. La mia domanda non può essere rappresentata come lista di lista (nella lista java dell'array della lista di array) o nella mappa di lista (in java HashMap con chiave come nodo e valore come lista di array di nodo connesso)?

In tutti e tre gli approcci citati vedo complessità temporale

Per scoprire se due nodi sono collegati - O (v) Per trovare tutti i nodi connessi - O (v)

Anche la complessità dello spazio sarà più o meno la stessa.

Allora perché l'Adjacency List è detta lista (o array) dell'elenco collegato non come lista di lista o mappa di lista?

    
posta user3198603 30.06.2018 - 17:52
fonte

1 risposta

0

Un elenco di liste o una mappa di lista o una mappa di mappa vanno bene per implementare un elenco di adiacenze. Nessun vero svantaggio per nessuno di loro. Personalmente uso un elenco di elenchi in Java ogni volta che ho bisogno di un grafico non pesato e un elenco di hashmap se ho bisogno di uno ponderato.

Per quanto riguarda il motivo per cui la lista di Adjacency viene definita come una serie di elenchi concatenati, non ho mai visto questo come uno standard d'oro ovunque. L' articolo wiki menziona tre implementazioni comuni e include sia elenchi collegati che matrici dinamiche.

    
risposta data 30.06.2018 - 21:08
fonte

Leggi altre domande sui tag