7.35

passes together still examine every vertex and edge at most twice, so the running time is

(a) Testing whether a given vertex v is a mother vertex (time [math]O(n+m)[/math])
Perform one reachability search from v. If all vertices are reached, v is a mother vertex.

// true ⇔ v is a mother vertex function isMother(G, v):
visited = ∅
stack = [v]
while stack ≠ ∅:
u = stack.pop()
if u ∉ visited:
visited.add(u)
for each (u, w) ∈ E: stack.push(w)
return |visited| = n


(b) Detecting whether the graph contains any mother vertex (time [math]O(n+m)[/math])
1. Run a full DFS of G, keeping the last vertex that finishes; call it c.
2. Run a second DFS starting from c. If it reaches every vertex, c (and thus a mother vertex) exists; otherwise no mother vertex exists.

function hasMother(G):
visited = ∅
candidate = null
for u in V: // first DFS pass
if u ∉ visited:
DFS_visit(u) // standard recursive DFS
candidate = u // finishes last in this call

visited = ∅ // verification pass
DFS_visit(candidate)
return |visited| = n // true ⇔ graph has a mother vertex


Correctness: in DFS the last finished vertex is in a source strongly-connected component that reaches all other components, hence if a mother vertex exists it must lie there; the second pass confirms reachability. Both algorithms examine every edge and vertex at most twice, giving linear time and [math]O(n)[/math] memory.

[math]\mathcal{O}(n+m)[/math]. The correctness follows because any true mother must be able to reach the start vertex of every DFS tree created in the first pass, hence must be the one that finishes last.

Back to Chapter 7