Solution: Depth-First Search
Explore solving a real-world problem by applying depth-first search and Kosaraju’s algorithm to test strong connectivity in directed graphs. Understand graph modeling, algorithm logic, and implement the solution in C++, enhancing your ability to analyze graph-based problems efficiently.
We'll cover the following...
Let's practice what we've learned so far.
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 is 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, describe and analyze the given algorithm to solve it, and then give its C++ 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 be the directed graph representing the city, where is the set of vertices (intersections) and is the set of directed edges (one-way ...