Graph Search Problem: Modify the Goal

  • Describe a variant of the general Graph Search problem that finds a path between a source and every reachable vertex.

Recall:

General Graph Search Problem

Input: Graph $G=(V, E)$, and a starting vertex $s \in V$.
Goal: Identify the vertices in $V$ reachable from $s$ in $G$.

We slightly modify the objective as follows:

Goal: Identify a path from $s$ to each (reachable) vertex in $G$.

We will see how we can modify the solution to the General Graph Search Problem to solve the modified version of it.