Graph Search: Definition

  • State the general graph search problem.

The Graph Search problem, in a nutshell, is figuring out if a graph contains a path from one vertex to another.

Many fundamental algorithms on graphs (e.g., finding shortest path, cycles, connected components, $\dots$) are applications of the graph search problem.

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$.

For example, consider the following graph: (It's one graph with multiple connected components!)

The set of vertices reachable from $s$ is $\{s, u, v, w\}$.