12 STRONGLY CONNECTED COMPONENTS

Previous chapters used connected components on undirected graphs to answer questions like “Can we get to a given location from here?” or “Would removing this edge break the graph’s connectivity?” Such questions and the algorithms that answer them become more complex once we start thinking about directionality. When examining reachability on a directed graph, it is no longer enough to say, “We can get from A to B.” We need to understand whether we can get back to A and, if not, how that impacts travel through the graph.

This chapter explores the concept of strongly connected components, sets of nodes in a ...

Get Graph Algorithms the Fun Way now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.