Wat is een geschikte manier om een ijle graaf, een graaf met weinig kanten in verhouding tot het aantal knopen, in het geheugen op te slaan, zoals een wegennet met ongeveer 1 miljoen knopen en 3 miljoen kanten?

Antwoord: B. Adjacentielijsten: het geheugen is evenredig met het aantal knopen plus het aantal kanten, en ze zijn geschikt om de kanten vanuit een knoop één voor één te volgen

Een adjacentiematrix gebruikt voor V knopen een tabel van V × V, dus 1 miljoen knopen vragen 10¹² elementen, ongeveer 125 GB, zelfs met 1 bit per element. Adjacentielijsten bevatten per knoop alleen de buren, dus het geheugen is O(V + E), in dit voorbeeld maar enkele miljoenen elementen. Een adjacentiematrix heeft het voordeel dat een kant in O(1) kan worden gecontroleerd, en is geschikt voor dichte grafen of grafen met weinig knopen. Voor bewerkingen die de kanten vanuit elke knoop één voor één volgen, zoals breedte-eerst zoeken en het algoritme van Dijkstra, zijn adjacentielijsten efficiënter.