[prev] 3 [next]

Transitive Closure (cont)

How to compute transitive closure?

One possibility:

  • implement it via hasPath(s,t)   (itself implemented by DFS or BFS algorithm)
  • feasible if reachable(g, s,t) is infrequent operation
What if we have an algorithm that frequently needs to check rechability?

Would be very convenient/efficient to have 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.