Ein Knoten (engl. Vertex oder Node) ist das Grundelement einer Graph-Datenstruktur: Er repräsentiert ein einzelnes Objekt und wird über Kanten mit anderen Knoten verbunden. Ein Baum ist ebenfalls ein Graph — seine Knoten stehen in Eltern-, Kind- und Geschwister-Beziehungen, siehe Baum-Datenstruktur.
Eigenschaften von Knoten
- Grad: Anzahl der Kanten, die an einem Knoten angrenzen; in gerichteten Graphen unterscheidet man eingehenden und ausgehenden Grad.
- Adjazente Knoten: direkt benachbarte Knoten, die über eine Kante verbunden sind.
- Isolierter Knoten: hat den Grad 0 und ist mit keinem anderen Knoten verbunden.
Wie Knoten gespeichert werden
Graphen werden meist als Adjazenzliste (für jeden Knoten die Liste seiner Nachbarn) oder als Adjazenzmatrix (Tabelle mit Zeilen und Spalten je Knoten) abgebildet. Beide Darstellungen drehen sich um die Frage, welche Knoten durch Kanten verbunden sind.
Knoten durchsuchen
Die beiden klassischen Suchstrategien starten an einem Startknoten: Die Tiefensuche geht erst in die Tiefe, die Breitensuche breitet sich Ebene für Ebene aus. Strukturen wie der Binärbaum bestehen aus speziellen Knoten mit maximal zwei Kindern.
Knoten in der Praxis
- Netzwerk-Geräte (Router, Switches) als Knoten eines Kommunikationsnetzes
- Personen in sozialen Netzwerken als Knoten, Freundschaften als Kanten
- Zustände in Zustandsautomaten oder Aufgaben in Abhängigkeitsgraphen
Algorithmen wie Union-Find verwalten Gruppen solcher Knoten effizient.
Verwandte Grundlagen: Graph-Datenstruktur, Baum-Datenstruktur, Adjazenzliste, Adjazenzmatrix, Tiefensuche, Breitensuche.