[prev] 15 [next]

Transitive Closure (cont)

One possibility:
  • implement it via hasPath(G,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 reachability?

Would be very convenient/efficient to have: 

reachable(G,s,t):
|  return G.tc[s][t]   // transitive closure matrix

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