[prev] [index] [next]

Reachability (cont)

How to implement an efficient reachability test?

One possibility:

  • implement it via hasPath(s,t)   (but v.expensive)
  • feasible if reachable(s,t) is infrequent operation
Another possibility - a look-up table: 

int reachable(Graph g, Vertex s, Vertex t)
{
    return (g->tc[s][t]);
}

Of course, if V is very large, then this is not feasible.