Knotenbesuche

Knotenbesuche bezeichnet in der Graphentheorie die Ereignisse, bei denen ein Knoten eines Graphen während der Ausführung eines Traversierungs- oder Suchverfahrens vom Algorithmus verarbeitet wird. Typischerweise wird ein Knoten beim ersten Auftreten markiert und in eine Struktur wie eine Warteschlange (BFS) oder einen Stack (DFS) aufgenommen, und erst dann als besucht gezählt. Ziel ist es, Mehrfachbesuche zu vermeiden; in gut implementierten Algorithmen wird jeder Knoten höchstens einmal besucht.

Nach der Terminologie der gängigen Traversierungs- bzw. Suchalgorithmen entspricht ein Knotenbesuch dem Moment, in dem der Knoten zum Verarbeiten ausgewählt wird. In BFS geschieht dies beim Herausnehmen aus der Warteschlange; in DFS beim Verarbeiten eines Knotens, nachdem er vom Stack oder rekursiv aufgerufen wurde. Die Anzahl der Knotenbesuche in einem Graphen mit V Knoten und E Kanten entspricht in der Regel der Anzahl der erreichbaren Knoten, also der Größe des betrachteten Teilgraphen.

Die Gesamtkosten der Traversierung werden durch die Knotenbesuche zusammen mit der Bearbeitung der Kanten bestimmt und üblicherweise als O(V+E) Zeit und O(V) Speicher angegeben. Falls Knoten mehrfach besucht würden (z. B. ohne Markierung), könnten die Kosten erheblich steigen oder die Suche in Zyklen endlos fortgesetzt werden. Die Markierung oder das Setzen eines Besucht-Flags verhindert dies.

Anwendungsfelder sind Pfadfindung, Erkennung von Zusammenhangskomponenten, Netzwerkanalyse sowie allgemeine Graph-Explorationen in KI-Algorithmen. Knotenbesuche dienen zudem als Metrik zur Messung des Fortschritts oder der Effizienz einer Traversierung.

Siehe auch: Graph, Traversierung, BFS, DFS, Suchalgorithmen.

---