Reachability
) if there exists a sequence of adjacent vertices (i.e. a walk) which starts with
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).
is acyclic, then its reachability relation is a partial order; any partial order may be defined in this way, for instance as the reachability relation of its transitive reduction.
is directed but not acyclic (i.e. it contains at least one cycle), then its reachability relation will correspond to a preorder instead of a partial order.
[3] Algorithms for determining reachability fall into two classes: those that require preprocessing and those that do not.
If you have only one (or a few) queries to make, it may be more efficient to forgo the use of more complex data structures and compute the reachability of the desired pair directly.
In exchange for preprocessing time and some extra storage space, we can create a data structure which can then answer reachability queries on any pair of vertices in as low as
Three different algorithms and data structures for three different, increasingly specialized situations are outlined below.
The Floyd–Warshall algorithm[5] can be used to compute the transitive closure of any directed graph, which gives rise to the reachability relation as in the definition, above.
This algorithm is not solely interested in reachability as it also computes the shortest path distance between all pairs of vertices.
For graphs containing negative cycles, shortest paths may be undefined, but reachability between pairs can still be noted.
For planar digraphs, a much faster method is available, as described by Mikkel Thorup in 2004.
[6] This method can answer reachability queries on a planar graph in
This algorithm can also supply approximate shortest path distances, as well as route information.
, the algorithm begins by organizing the vertices into layers starting from an arbitrary vertex
, three separators are identified which, when removed, break the graph into three components which each contain at most
provides for a natural indexing of its vertices from the start to the end of the path.
From this point, a logarithmic time query for reachability is as simple as looking over each pair of labels for a common, suitable
The original paper then works to tune the query time down to
The separator phase of the algorithm breaks the graph into components which are at most
the size of the original graph, resulting in a logarithmic recursion depth.
At each level of the recursion, only linear work is needed to identify the separators as well as the connections possible between vertices.
An even faster method for pre-processing, due to T. Kameda in 1975,[7] can be used if the graph is planar, acyclic, and also exhibits the following additional properties: all 0-indegree and all 0-outdegree vertices appear on the same face (often assumed to be the outer face), and it is possible to partition the boundary of that face into two parts such that all 0-indegree vertices appear on one part, and all 0-outdegree vertices appear on the other (i.e. the two types of vertices do not alternate).
extra bits per vertex, answering reachability queries for any pair of vertices in
During this traversal, the adjacency list of each vertex is visited from left-to-right as needed.
As vertices are popped from the traversal's stack, they are labelled with the value
The depth-first traversal is then repeated, but this time the adjacency list of each vertex is visited from right-to-left.
A related problem is to solve reachability queries with some number
The breadth-first search technique works just as well on such queries, but constructing an efficient oracle is more challenging.
