The reachability problem for a graph is the following problem:
Given two vertices a and b in a graph, is it possible to go from vertex a to vertex b following only edges in the graph? In other words, is there a sequence of verticesv0, v1, ..., vnsuch that:
- v0 = a;
- vn = b; and
- for each i (0 <= i < n), there is an edge between vertices vi and vi+1.
This specifies a natural recursive algorithm for determining reachability. The problem with this algorithm, as stated, is that it can get into an infinite loop when processing a cycle. As an example, consider the figure shown above. Suppose we want to know whether vertex j is reachable from e. One possible execution of the algorithm above might be as follows:
is j reachable from e?
is j reachable from f? [using the edge between
e and f]
is j reachable from g?
[using the edge between f and g]
is j reachable from h?
[using the edge between g and h]
is j reachable from f?
[using the edge between h and f]
...
and the execution is stuck in a loop.
We can fix the problem by marking each vertex as we visit it, and making sure that we never visit a marked vertex a second time. To determine whether a vertex B is reachable from a vertex A, the algorithm now is:
- mark all vertices ``unvisited'';
- return Reachable(A, B).
where the function Reachable() is defined as follows:
function Reachable(vertex x, vertex y)
end /* Reachable */
- if x == y return TRUE;
- else for each unvisited neighbor z of x do:
- mark z ``visited'';
- if Reachable(z, y) return TRUE.
Note that the step ``mark all vertices unvisited'' is done outside the function Reachable(), and has to be carried out for each query processed.