Abstract
We survey three algorithms that use depth-first search to find the strong components of a directed graph in linear time: (1) Tarjan's algorithm; (2) a cycle-finding algorithm; and (3) a bidirectional search algorithm.
Finding Strong Components Using Depth-First Search
Related papers
- Engineering DFS-Based Graph Algorithms (2017)β
- Graph Searches and Their End Vertices (2019)β
- Space Efficient Algorithms for Breadth-Depth Search (2019)β
- Graph Search Trees and Their Leaves (2023)β
- Space-Efficient DFS and Applications: Simpler, Leaner, Faster (2018)β
- Enumerating Graph Partitions Without Too Small Connected Components Using Zero-suppressed Binary and Ternary Decision Diagrams (2018)β
- Nearly Optimal Space Efficient Algorithm for Depth First Search (2018)β
- Decomposing Triangulations into 4-Connected Components (2023)β