From direct edges to reachability
Edges A→B and B→C make A→C reachable even without a direct edge. Closure summarizes the existence of multi-step paths rather than constructing a physical new route.
The positive-step transitive closure is commonly written R⁺; adding identity pairs gives reflexive-transitive closure R*. Graph libraries sometimes count zero-step self-reachability, so a true diagonal entry need not establish a nonempty cycle.
Caching reachability from each source
A direct algorithm searches from every vertex and stores the resulting reachable set. Queries then read the marks associated with the source. Princeton’s directed search marks its source immediately, including zero-step self-reachability.
V adjacency-list searches take O(V(V+E)) time, while all-pairs Boolean storage takes O(V²) space. A sparse original graph can still have a dense closure: even a directed chain has quadratically many reachable pairs.
Accounting for output size and query needs
For occasional queries from a few sources, on-demand searches can avoid storing every pair. Repeated queries on a static graph may justify preprocessing, while updates require maintaining or invalidating old results.
Closure depends on the supplied relation. A multi-step employment, citation or transaction path need not imply the same direct domain relationship between its endpoints. A Boolean reachability result also does not supply path length or the actual intervening evidence.