Transitive Closure (cont)
Cost analysis (tc[][]):
- storage: additional V2 items (each item may be 1 bit)
- computation of
makeClosure(): V3 on first call to reachable()
- computation of
reachable(): O(1) after first call to reachable()
Amortization: many calls to reachable() would justify other costs
Alternative: use DFS in each call to reachable()
Cost analysis (DFS):
- storage: cost of queue and set during reachable
- computation of
reachable(): O(V2) (for adj matrix)
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}