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

Data Structures

Graph Search: Definition