Graphen: Adjazenzliste

Ein Graph besteht aus Knoten und Kanten. Eine knotenweise Nachbarschaftsdarstellung speichert für jeden Knoten die Liste seiner Nachbarn. Sparse Graphen brauchen damit $O(n + m)$ Speicher.

Eine n x n-Matrix ist $O(n^{2})$ und schnell bei dichten Graphen und Kantenabfragen in $O(1)$.

In Java: Map> oder List>.

Gitter als Graph: Number of Islands [1].

Wo gebraucht

Soziale Netze, Microservice-Abhängigkeiten, Strassenkarten, Knowledge Graphs, Build-Dependency-Graphen. Adjazenzlisten dominieren bei sparse Graphen im Speicher.

Vertiefung

Bei der Nachbarlisten-Darstellung speichert jeder Knoten eine Sammlung direkt erreichbarer Ziele. Der Speicherbedarf ist proportional zur Zahl der Knoten plus Kanten und eignet sich daher besonders für dünn besetzte Graphen.

Das Aufzählen aller Nachbarn kostet proportional zum Grad des Knotens. Die Prüfung einer bestimmten Kante kann dagegen linear im Grad sein, sofern die Nachbarsammlung keine zusätzliche Hash- oder Suchstruktur besitzt.

Bei ungerichteten Graphen wird eine logische Kante häufig in beiden Richtungen gespeichert. Schleifen und parallele Kanten benötigen eine bewusste Modellentscheidung, weil sie Gradberechnung und Algorithmen beeinflussen.

Schwierigkeitsstufen

1. Nachbarsammlungen aus einer Kantenmenge aufbauen.
2. Speicher- und Abfragekosten nach Knotengrad analysieren.
3. Doppelspeicherung ungerichteter Kanten korrekt berücksichtigen.

Fallstricke

Die Zahl gespeicherter Einträge ist bei ungerichteten Kanten meist doppelt so gross wie die logische Kantenzahl. Eine fehlende Zielmenge für isolierte Knoten lässt diese aus dem Graphmodell verschwinden.