Graph-Reachability Problem

computation

Definition

Graph-Reachability Problem

Given a graph and vertices . The graph reachability problem asks whether there exists a path from to in .

The graph reachability problem is a decision problem.

Example

SIMPLE program for graph reachability

The following SIMPLE-style program computes the set of all vertices reachable from and then checks whether is among them.

S := {u};
repeat
    S' := S;
    for all i ∈ S' do {
        for all j ∈ V do {
            if (i,j) ∈ E then S := S ∪ {j};
        }
    }
until S = S';
if v ∈ S then return true;
else return false;

The set grows monotonically. When the loop stops, no new vertex can be added, so is exactly the set of vertices reachable from .