Lecture: Strong Components via Depth-First Search

Robert Endre Tarjan

In 1972 the speaker invented an algorithm to find the strong components of a directed graph in linear time. The algorithm illustrates the power of depth-first search in solving graph problems. This talk will present the algorithm, along with reflections fifty years later.

---