liste multiple

• una lista multipla, o multilista, è una lista concatenata la cui struttura dei nodi ha due o più link ad altri nodi
  • esempio già visto: le liste doppiamente concatenate
• le multiliste sono utili per strutture dati con più ordinamenti simultaneamente
  • ad esempio: una lista di elementi dei quali si voglia rappresentare sia l'ordine cronologico di inserimento nella lista sia un altro ordine, ad es. basato su un ordinamento definito sul tipo degli elementi
• è discutibile se, e in qual modo, le multiliste siano utili a rappresentare matrici multidimensionali sparse:
  • una matrice di elementi di un tipo in cui sia definito un valore nullo è detta sparsa se quasi tutti i suoi elementi sono nulli; nel caso opposto è detta densa
  • è evidente il risparmio di spazio nel rappresentare matrici sparse mediante liste, con un nodo per ogni elemento non nullo (e nessuno per quelli nulli)
  • naturalmente, un simile risparmio si paga con un maggior tempo di accesso
  • non è però evidente la convenienza, in generale, di avere tanti link per nodo quante sono le dimensioni della matrice (v. esercizi)

grafi: matrici di adiacenza

i grafi, strutture matematiche già familiari dall'analisi del problema della connettività, hanno una immediata rappresentazione con matrici di adiacenza: matrici binarie, in cui l'elemento (i,j) è 1 o 0 a seconda che esista o meno un arco dal vertice i al vertice j

• si assume di solito che la relazione binaria espressa dal grafo sia riflessiva, ossia che esista un arco (anche se non esplicitamente tracciato nel grafo) da ciascun vertice a sé stesso
• i bit sulla diagonale della matrice di adiacenza hanno dunque valore 1, per convenzione
• la rappresentazione con matrice di adiacenza ben si presta anche a grafi orientati: la matrice di adiacenza è simmetrica se il grafo non è orientato (relazione binaria simmetrica)
• di solito, se il grafo ha V vertici ed E archi, se ne rappresentano i vertici con i primi V numeri naturali e gli archi con corrispondenti E coppie di tali numeri

se il grafo ha pochi archi, ossia E << V², allora la matrice di adiacenza è sparsa, nel qual caso rappresentazioni alternative del grafo meritano considerazione

• non solo per il risparmio di spazio ma anche perché, per certi algoritmi, se ne ottiene un minor tempo di esecuzione

rappresentazione di grafi mediante liste

una rappresentazione dei grafi alternativa alla matrice di adiacenza si realizza mediante liste di adiacenza:

• si rappresenta un grafo di V vertici con un array di altrettanti puntatori a liste (unidimensionali): la lista di indice v contiene un nodo per ciascun vertice connesso da un arco al vertice v (l'ordine dei nodi in ciascuna lista è arbitrario)

con la rappresentazione mediante liste di adiacenza si perde, rispetto a quella della matrice di adiacenza, il vantaggio di poter determinare l'esistenza di un arco, fra due vertici dati, in tempo costante

tuttavia, non tutti gli algoritmi hanno in questo il fattore critico di prestazione in termini di tempo di esecuzione:

• ad esempio, per algoritmi che debbano frequentemente elaborare informazione relativa a tutti gli archi del grafo, una rappresentazione lineare in V+E, quale quella delle liste di adiacenza, può ben risultare vantaggiosa rispetto a quella della matrice di adiacenza, quadratica in V, se questa è sparsa

esercizi

il testo (Sedgewick, 2003), a p.121, suggerisce l'uso di una multilista per rappresentare una matrice multidimensionale sparsa, con un nodo per ogni elemento (non nullo) della matrice e un link per ogni dimensione, dove un link punta al successivo nodo per quella dimensione; questo suggerimento ha il difetto di presumere un unico ordinamento degli elementi della matrice per ciascuna dimensione:

1. mostrare che il risparmio di spazio suggerito dal testo è conseguibile mediante rappresentazione con una lista unidimensionale
2. in quanti modi può definirsi un ordinamento lessicografico degli elementi della matrice, determinato solo dai valori degli indici e basato su un ordinamento (totale) delle dimensioni, per una matrice N-dimensionale?
3. in quali casi l'uso di una multilista per la rappresentazione in questione può presentare vantaggi rispetto all'uso di una lista unidimensionale, e quali vantaggi?