Kurzimplementierung: Nachbarn zählen

Kleine Implementierungsübung: Grad eines Knotens in einer Adjazenzliste ist die Länge seiner Nachbarliste.

$$\mathrm{indeg}(v)=\lvert\{u:v\in N(u)\}\rvert$$

Wo gebraucht

Gradverteilung, Fan-in/Fan-out von Services, einfache Feature-Extraktion vor Ranking oder Anomalieerkennung.

Vertiefung

In einer Nachbarlisten-Struktur entspricht der Ausgangsgrad eines Knotens der Grösse seiner Nachbarsammlung. Bei gerichteten Graphen ist der Eingangsgrad nicht lokal am Ziel ablesbar, sofern keine Rückwärtslisten gepflegt werden.

Alle Eingangsgrade lassen sich in einem Durchlauf initialisieren und beim Durchlaufen jeder Kante am Ziel erhöhen. Die Gesamtkosten sind proportional zu Knoten plus Kanten. Wiederholte Einzelabfragen können zusätzliche Rückwärtsindizes rechtfertigen.

Die Semantik hängt vom Kantenmodell ab. Parallele Kanten zählen mit einer Liste mehrfach, mit einer Menge nur einmal. Eine Schleife trägt im gerichteten Fall je einmal zu Ein- und Ausgangsgrad bei.

Schwierigkeitsstufen

1. Ausgangsgrad direkt aus einer Nachbarsammlung lesen.
2. Alle Eingangsgrade in einem Kantendurchlauf berechnen.
3. Schleifen und Mehrfachkanten unter einer definierten Semantik behandeln.

Fallstricke

null für fehlende Nachbarn und eine leere Sammlung sind nicht dasselbe API-Verhalten. Graddefinitionen dürfen ausserdem nicht stillschweigend zwischen logischen und gespeicherten Kanten wechseln.