Reachability

In graph theory, reachability refers to the ability to get from one vertex to another within a graph. A vertex ${\displaystyle s}$ can reach a vertex ${\displaystyle t}$ (and ${\displaystyle t}$ is reachable from ${\displaystyle s}$) if there exists a sequence of adjacent vertices (i.e. a walk) which starts with ${\displaystyle s}$ and ends with ${\displaystyle t}$.

In an undirected graph, reachability between all pairs of vertices can be determined by identifying the connected components of the graph. Any pair of vertices in such a graph can reach each other if and only if they belong to the same connected component; therefore, in such a graph, reachability is symmetric (${\displaystyle s}$ reaches ${\displaystyle t}$ iff ${\displaystyle t}$ reaches ${\displaystyle s}$). The connected components of an undirected graph can be identified in linear time. The remainder of this article focuses on the more difficult problem of determining pairwise reachability in a directed graph (which, incidentally, need not be symmetric).