7.7

(a) Breadth-first search (BFS)
Graph: a star with centre v and the remaining n-1 vertices as leaves.
Execution: after v is dequeued its n-1 = Θ(n) neighbours are en-queued and marked discovered in the same step, so the queue (the set of discovered-but-unprocessed vertices) simultaneously contains Θ(n) vertices.

(b) Depth-first search (DFS)
Graph: a simple path v = x₁, x₂, … , x_n.
Execution: DFS started at v keeps recursing along the path. Before any back-tracking occurs every vertex encountered is only discovered, not processed, so after reaching x_n all n vertices are simultaneously in the recursion stack – Θ(n) discovered vertices at once.

(c) DFS with Θ(n) processed and Θ(n) still undiscovered
Graph: let v be the root of two disjoint chains   • first chain  v – a₁ – a₂ – … – a_k   • second chain v – b₁ – b₂ – … – b_k, with k = (n-1)/2 = Θ(n) (ignore the ±1 detail if n is odd).
Tie-breaking makes DFS visit the entire a-chain before the b-chain.
State just after finishing the recursive call that returns from a₁:
  • Vertices a₁ … a_k are already processed ⇒ Θ(n) processed.
  • Vertices b₁ … b_k have not been touched yet ⇒ Θ(n) still undiscovered.
  • v (and possibly the current edge) is merely discovered.
Thus at that moment the DFS simultaneously satisfies the required Θ(n) counts for both processed and undiscovered vertices.

Back to Chapter 7