Wie lässt sich ein dünn besetzter Graph, also einer mit wenigen Kanten im Verhältnis zur Zahl der Knoten, etwa ein Straßennetz mit rund 1 Million Knoten und 3 Millionen Kanten, geeignet im Speicher ablegen?

Antwort: B. Als Adjazenzlisten: Der Speicherbedarf ist proportional zur Zahl der Knoten plus der Zahl der Kanten, und sie eignen sich, um die von einem Knoten ausgehenden Kanten der Reihe nach zu verfolgen

Eine Adjazenzmatrix verwendet für V Knoten eine Tabelle mit V × V Einträgen; 1 Million Knoten brauchen also 10¹² Einträge, selbst bei 1 Bit pro Eintrag etwa 125 GB. Adjazenzlisten speichern nur die Nachbarn jedes Knotens, der Speicherbedarf ist also O(V + E), in diesem Beispiel nur einige Millionen Einträge. Eine Adjazenzmatrix hat den Vorteil, eine Kante in O(1) prüfen zu können, und eignet sich für dicht besetzte Graphen oder Graphen mit wenigen Knoten. Für Verfahren, die nacheinander die von jedem Knoten ausgehenden Kanten verfolgen, etwa die Breitensuche und den Dijkstra-Algorithmus, sind Adjazenzlisten effizienter.