\( \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\R}{\mathbb{R}} \newcommand{\val}{\textnormal{val}} \newcommand{\dist}{\textnormal{dist}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\N}{\mathbb{N}} \)

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

Problem ($s$-$t$-Erreichbarkeit)Gegeben ein gerichteter Graph $G = (V,E)$ und zwei Knoten $s, t \in 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 Mit Tiefensuche kann man $s$-$t$-Erreichbarkeit in $O(n)$ Zeit lösen.