Challenge: Depth-First Search
Explore how to model city intersections as a directed graph and use depth-first search alongside Kosaraju’s algorithm to verify strong connectivity. Learn to implement these graph algorithms in Python to determine if all intersections are reachable from one another according to the mayor’s claim.
We'll cover the following...
Let's practice what we have 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, and then describe and analyze the given algorithm to solve it and then give its Python 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 streets).
The mayor’s claim states that it is possible to legally drive from any intersection to any other intersection. In graph theory terms, we need to verify if the directed graph ...