directed reachability
Concept
Directed reachability
- whether there is a path fron one vertex to another
- using DFS
Reachable(G,s):
DFS(G,s)
return visited
At the end of DFS(G,s), visited[v] is true iff s~v(path from s to v)
==>
Base: s~s
Step: let u be the vertex we are exploring when we set visited[v] = true
By IH, s~> u and u~>v thus s~>v
<==
let s = v_0v_1…v_k = v be a path in G
prove that visited[v_i]=true
Base: visited[s]<- true
Step:
by IH, visited[v_{i-1}] if true
so we explore v_{i-1}
v_i is a neighbour of v_{i-1}, when v_i is processed we set visited[v_i] to true if it has not yet been set to true earlier
Reversed graph
graph reversal is O(m)
Reversal lemma
- path in the graph implies the opposite path in the reversed graph
proof
u = v_0 v_1 … v_k be a path in G iff v=v_k … v_1 v_0 = u is a path in G’
so looking for u~>G v and u~>{G^R} v is effectively u~>_G v and v~>_G u