Erreichbarkeitsprobleme

Erreichbarkeitsprobleme bezeichnen in der Informatik die Frage, ob in einem Graphen zwischen zwei Knoten ein Pfad existiert. Dabei kann es sich um gerichtete Graphen handeln, bei denen die Richtung der Kanten relevant ist, oder um ungerichtete Graphen. Typische Fragestellung ist: Ist von s der Knoten t erreichbar? In vielen Anwendungen kommen weitere Einschränkungen hinzu, etwa Kantengewichte, maximale Pfadlängen oder Pflichtknoten.

Varianten: Einzelne Abfrage (s, t) gegenüber All-Pairs-Reachability, bei der für alle Knotenpaare bestimmt wird, ob eine Verbindung besteht. Die transitive Hülle eines Graphen fasst alle erreichbaren Paare zusammen und dient als Grundlage für schnellere Antworten auf Mehrfachanfragen.

Algorithmen: Für eine einzelne Abfrage reichen BFS oder DFS, die in linearer Zeit O(n + m) arbeiten (n Knoten, m Kanten). Für viele Anfragen oder All-Pairs-Reachability eignen sich der Warshall-Algorithmus (Transitive Closure) in O(n^3) oder wiederholte BFS-Durchläufe; bei großen Graphen gibt es spezialisierte dynamische Algorithmen.

Komplexität und Theorie: Das Grundproblem lässt sich in polynomialer Zeit lösen. In der theoretischen Informatik gehört Erreichbarkeit zu den klassischen Problemen; in bestimmten Modellen wird sie in NL klassifiziert, praktisch liefern BFS/DFS jedoch sehr effiziente Verfahren.

Anwendungen: Netzwerkanalyse und Routing, soziale Netzwerke, Programm- und Systemanalyse (Kontrollflussgraphen), Abhängigkeits- und Datenflussgraphen, Verifikation und formale Spezifikationen.

Siehe auch: BFS, DFS, Transitive Closure, Warshall, Graphentheorie.

---