Nachbarknoten

Nachbarknoten, auch Nachbarn eines Knotens genannt, bezeichnet in der Graphentheorie jeden Knoten, der durch eine direkte Kante mit einem gegebenen Knoten verbunden ist. In einfachen ungerichteten Graphen entspricht jeder Nachbarknoten einem Knoten, der durch dieselbe Kante mit dem Ausgangsknoten verbunden ist. In gerichteten Graphen unterscheidet man ausgehende Nachbarn (Out-Nachbarn) und eingehende Nachbarn (In-Nachbarn).

Formal lässt sich ein Graph G=(V,E) beschreiben. Für einen Knoten v∈V sind die Nachbarn von v die Knoten u ∈ V mit der Kante (u,v)∈E (In-Nachbarn) bzw. die Knoten w ∈ V mit der Kante (v,w)∈E (Out-Nachbarn). Die Anzahl der Nachbarn eines Knotens wird als Grad bezeichnet: deg(v) im ungerichteten Fall; in gerichteten Graphen deg_in(v) und deg_out(v). Isolierte Knoten haben keine Nachbarn.

Gängige Datenstrukturen zur Speicherung von Nachbarbeziehungen sind Adjazenzenlisten, die für jeden Knoten die Nachbarn auflisten, oder Adjazenzenmatrizen, in denen Nachbarn durch Einsen markiert werden. In vielen Algorithmen wird explizit über Nachbarknoten iteriert, zum Beispiel bei Such- und Traversierungsverfahren (Breitensuche, Tiefensuche) oder bei Pfad- und Distanzberechnungen (Dijkstra, Bellman-Ford).

Zu beachten sind Besonderheiten wie Mehrfachkanten oder Schleifen in gerichteten oder ungerichteten Graphen; je nach Definition werden Schleifen als eigene Nachbarn gezählt oder ignorierrt. Nachbarknoten sind zentrale Konzepte in Netzwerken, sozialen Strukturen und vielen graphentheoretischen Algorithmen.