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)G=(V, E), and a starting vertex s∈Vs \in V.
Goal: Identify the vertices in VV reachable from ss in GG.

We slightly modify the objective as follows:

Goal: Identify a path from ss to each (reachable) vertex in GG.

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