Part VI · Graph Algorithms and Tree-Graph Techniques
38. Connectivity, Bridges, Articulation Points and SCCs
6 lessons•25 topics•Intermediate / Advanced
6 of 6 lessons published
38.015 animated
DFS timestamps
- tin and tout
- Low-link value
- Back edges
- Tree edges
- Edge cases for multigraphs
38.024 animated
Bridges
- Tarjan low-link bridge detection
- 2-edge-connected components
- Bridge tree
- Critical connections
38.034 animated
Articulation points
- Root exception
- Low-link criterion
- Biconnected blocks
- Block-cut tree
38.044 animated
Strongly connected components
- Kosaraju
- Tarjan SCC
- SCC condensation DAG
- Component ordering
38.054 animated
2-SAT
- Implication graph
- Variable/negation nodes
- SCC unsatisfiable condition
- Assignment construction
38.064 animated
Graph robustness
- Bridge removal
- Articulation removal
- Connectivity augmentation
- Edge-biconnectivity intro