Qual è il modo più efficiente in termini di spazio per implementare una struttura di dati del grafico?

Bene, se l'efficienza dello spazio è tutto ciò che ti interessa, una struttura di dati compresso sarebbe la soluzione migliore, ma ovviamente non è molto efficiente per l'accesso o l'aggiornamento .....

Se il tuo grafico ha un numero relativamente piccolo di nodi ed è abbastanza denso (diciamo che esiste almeno il 5% di tutte le connessioni possibili), allora potresti trovare che è più efficiente nello spazio creare un matrice di adiacenza anziché utilizzare gli elenchi di spigoli. Ciò richiederebbe solo un bit per la connessione (diretta) possibile, e n * n bit totali dove hai n nodi.

Altrimenti, se hai bisogno di usare i link adiacenti, non puoi facilmente fare meglio di un riferimento per link poiché questo è il contenuto minimo di informazioni che devi memorizzare. Se vuoi i back-link ti occorrono il doppio dei link.

Ci sono alcuni trucchi che potresti provare sopra. Ad esempio, puoi provare a condividere sottoinsiemi di link (se A e B si riferiscono a ciascuno di C, D, E quindi memorizza solo la lista dei link C, D, E una volta .....). Tuttavia questo diventerà abbastanza complesso e dubito che ne varrà la pena nella maggior parte dei casi.

Un altro trucco: supponendo che il tuo grafico abbia un numero ragionevole di nodi, risparmierai sicuramente spazio indicizzando, ad es. utilizzando un numero di indice del nodo a 16 bit anziché un puntatore / riferimento completo.

Dipenderà dalla struttura dei tuoi dati.

Per un grafico denso con bordi non orientati, non è possibile battere realmente un elenco di matrici di bit che rappresentano una matrice triangolare. Un List<BitArray> per esempio. Logicamente, sarebbe simile a questo:

 0123
0
11
211
3001
41010

Da lì, puoi usare l'indice del root BitArray per indicizzare in un elenco che memorizza i dati del tuo nodo.

Ad esempio, ottenere tutti i vicini di un nodo equivale a:

// C#
List<Node> Nodes = /* populated elsewhere */
List<BitArray> bits = /* populated elsewhere */
public static IEnumerable<Node> GetNeighbours(int x)    
{
    for (int i = 0; i < bits[idx].Count; i++)
    {
        if (this.bits[idx][i])
            yield return this.Nodes[i];
    }

    for (int i = 0; i < this.Nodes.Count; i++)
    {
        if (idx < this.bits[i].Count && this.bits[i][idx])
            yield return this.Nodes[i];
    }    
}

(nota che puoi anche scegliere il tipo di indice, a seconda della quantità di dati, per essere un byte o un ushort o qualcosa del genere in quanto tutti gli indici saranno positivi. Non considero questo un micro-ottimizzazione come è banale)

Per un grafico diretto, si andrebbe a trovare un array di bit * n per archiviare la connettività ... a meno che non sia molto scarso rispetto al numero di nodi, dove si può andare a un elenco di indici di adiacenza.