I typically implement graphs as doubly linked lists but this is fairly space inefficient in my experience as I need k pointers/references for k neighbors so for an undirected graph I'd have ~2k neighbor links within the lists if my math is right. Is there a better way of saving space? I know that some of the links can be made singular if the graph is directed but is there a way to do a better job of this?
Space Efficient Graph Data Structure – Best Implementation Methods
data structures
Related Topic
- Data Structures – Efficient Structures for Holding a Graph in C++
- C# – Most efficient data structure for implementing inheritance structure without classes
- Efficient data structure to implement fake file system
- Data Structures – Most Efficient Way to Store Data
- Workaround for implementing operations on doubly linked or circular data structures in languages with immutable data
- Data Structures – Most Efficient Way to Store Data (CSV, Flat Files, Tree Structure)
- Data Structures – Most Efficient Way to Store a Numeric Range
Best Answer
Well if space efficiency is all you care about then a compressed data structure would be best - but of course this isn't very efficient for access or update.....
If your graph has a relatively small number of nodes and is fairly dense (lets say at least 5% of all possible connections exist) then you may find it is more space efficient to create an adjacency matrix rather than using edge lists. This would require just one bit per possible (directed) connection, and n*n bits total where you have n nodes.
Otherwise if you need to use neighbour links then you can't easily do better than one reference per link since this is the minimum information content you need to store. If you want back-links you will need twice as many links.
There are some tricks you could try on top of this. For example, you could try sharing subsets of links ( if A and B refer to each of C, D, E then only store the list of links C,D,E once.....). However this will get complex pretty quickly and I doubt it will be worth the effort in most cases.
One other trick - assuming your graph has a reasonable number of nodes, you will certainly save space by indexing - e.g. using a 16-bit node index number rather than a full pointer / reference.