Solution: Depth-First Search

Task

The police department in the city of Sham-Poobanana has made every street in the city one-way. Despite widespread complaints from confused motorists, the mayor claims that it’s possible to legally drive from any intersection in Sham-Poobanana to any other intersection. The city needs to either verify or refute the mayor’s claim. Formalize this problem in terms of graphs, and then describe and analyze the given algorithm to solve it; and then give its Java implementation.

Logic building

To formalize the problem in terms of graphs, we can model the intersections and streets of Sham-Poobanana as a directed graph. In this graph, each intersection will be represented by a vertex (node), and each one-way street will be represented by a directed edge (arc) between two vertices.

Let $G = (V, E)$ be the directed graph representing the city, where $V$ is the set of vertices (intersections) and $E$ is the set of directed edges (one-way streets).

The mayor’s claim states that it is possible to legally drive from any intersection to ...