= Infinite walk criterion in a finite directed graph
A finite <directed graph> admits an infinite edge-following walk from $s$ exactly when a <directed cycle> is reachable from $s$. An infinite walk repeats a <vertex> and therefore contains a reachable cycle; conversely, reach a cycle and repeat it. In a <strongly connected component>, a cycle exists precisely when the component has at least two vertices or is a singleton with a self-loop. Reachability followed by the <two-pass strongly connected component algorithm> decides the criterion in $O(|V|+|E|)$ time.
The nonempty set of vertices visited infinitely often by a single infinite walk lies within one <strongly connected component>. For two such vertices, arbitrarily late visits supply directed walks in both directions. This set need not be the whole component: the walk can keep choosing one cycle and omit other vertices.
Back to article page
