Transitive Closure (cont)
How it works …
After iteration 1, tc[s][t] is 1 if
- either s→t exists or s→0→t exists
After iteration 2, tc[s][t] is 1 if any of the following exist
- s→t or
s→0→t or
s→1→t or
s→0→1→t or
s→1→0→t
Etc. … so after the Vth iteration, tc[s][t] is 1 if
- there is any directed path in the graph from s to t
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}