Transitive Closure (cont)
Cost analysis:
- storage: additional V2 items (each item may be 1 bit)
- computation of transitive closure: O(V3)
- computation of
reachable(): O(1) after having generated tc[][]
Amortisation: would need many calls to reachable() to justify other costs
Alternative: use DFS in each call to reachable()
Cost analysis:
- storage: cost of stack and set ("visited") during
reachable()
- computation of
reachable(): cost of DFS = O(V2) (for adjacency matrix)
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}