4.3 Sequentielle Algorithmen für Erreichbarkeit

Das Problem der s-t-Erreichbarkeit in gerichteten Graphen ist selbst für sequentielle Algorithmen interessanter, als es scheint. Hier nochmal das Problem:

Problem 4.3.1 (s-t-Erreichbarkeit)Gegeben ein gerichteter Graph G=(V,E) und zwei Knoten s,t∈V: gibt es einen Pfad von s nach t?

Einer der ersten Graphenalgorithmen, die Sie kennengelernt haben, ist wahrscheinlich die Tiefensuche; diese ist eher eine algorithmische Idee als ein konkreter Algorithmus. Eines der vielen Probleme, die sie lösen kann, ist s-t-Erreichbarkeit. Ihre Laufzeitkomplexität ist O(n).

Theorem 4.3.2 Mit Tiefensuche kann man s-t-Erreichbarkeit in O(n) Zeit lösen.