Bridges and Articulation Points
(Critical edges and vertices)
Lessons
1. Intro
Finding weak spots in networks
2. What is a Bridge?
Edge whose removal disconnects
3. Bridge Example
(Visualizing critical edges)
4. Why Bridges Matter
Network reliability applica...
5. What is an Articulation Point?
Vertex whose removal discon...
6. Articulation Point Example
Visualizing critical vertices
7. DFS Tree and Back Edges
Foundation for Tarjan's algo
8. DFS Tree Example
(Tree edges vs back edges)
9. Why Back Edges Prevent Bridges
Cycles provide alternate paths
10. Discovery Time
(When DFS first visits vertex)
11. Low-Link Value
(Earliest reachable ancestor)
12. Low-Link Intuition
(Can you escape the subtree?)
13. Low-Link Example
Computing values step by step
14. Quiz: Low-Link Values
Knowledge check
15. Tarjan's Algorithm for Bridges
(One-pass DFS solution)
16. Bridge Detection Logic
(When is an edge a bridge?)
17. Tarjan Bridge Pseudocode
(DFS with discovery and low)
18. Bridge Algorithm Walkthrough
(Step-by-step execution)
19. Quiz: Bridge Detection Condition
Knowledge check
20. Tarjan's Algorithm for Articulation Points
(Finding critical vertices)
21. Articulation Point: Root Case
(Root with multiple children)
22. Articulation Point: Non-Root Case
(Child cannot bypass parent)
23. Articulation Point Pseudocode
(DFS with discovery and low)
24. Articulation Point Walkthrough
(Step-by-step execution)
25. Quiz: Articulation Point Rules
Knowledge check
26. Vocabulary - Critical Connection
(Bridge in network graph)
27. Problem - Critical Connections in a Network
(LeetCode 1192)
28. Critical Connections - Input Example
(Visualizing the network)
29. Critical Connections - Core Idea
Apply Tarjan's bridge algo
30. Critical Connections - Algorithm
(Tarjan's bridge detection)
31. Critical Connections - Implementation
(Python with DFS)
32. Critical Connections - Trace
(Running Tarjan's algorithm)
33. Critical Connections - Time Complexity
(Linear in edges)
34. Critical Connections - Edge Cases
(Single edge and cycles)
35. Critical Connections - Lessons
(What you learned)
36. Vocabulary - 2-Edge-Connected Component
(Maximal set without bridges)
37. Building 2-Edge-Connected Components
(Contract non-bridge edges)
38. 2-Edge-Connected Components Example
(Visualizing the structure)
39. Quiz: $2$-Edge-Connected Components
Knowledge check
40. Problem - Finding Articulation Points
(Critical vertices in network)
41. Articulation Points - Input Example
(Graph with critical vertices)
42. Articulation Points - Core idea
Apply Tarjan's vertex algo
43. Articulation Points - Algorithm
(DFS-based detection)
44. Articulation Points - Implementation
(Python with DFS)
45. Articulation Points - Trace
(Step-by-step execution)
46. Articulation Points - Time Complexity
(Linear in edges)
47. Articulation Points - Edge Cases
Single vertex and complete ...
48. Articulation Points - Lessons
(What you learned)
49. Quiz: Tarjan's Algorithm Complexity
Knowledge check
50. Application - Network Reliability
Identifying single points o...
51. Application - Graph Partitioning
Dividing graphs at weak points
52. Application - Circuit Design
(Fault tolerance in circuits)
53. Vocabulary - Biconnected Component
Maximal subgraph without ar...
54. Building Biconnected Components
(Using edge stack during DFS)
55. Bridge Trees
Condensing 2-edge-connected...
56. Quiz: Bridge Trees
Knowledge check
57. Bridge Tree Example
(Condensing a graph)
58. Section Recap
(What you learned)