Articulation Points (Cut Vertices)
Find vertices whose removal disconnects the graph. Critical for network reliability. Uses DFS with low-link values. O(V+E) Tarjan's algorithm.
Visualization
Interactive visualization for Articulation Points (Cut Vertices)
Interactive visualization with step-by-step execution
Implementation
1class ArticulationPoints {
2 private time = 0;
3 private disc: Map<number, number> = new Map();
4 private low: Map<number, number> = new Map();
5 private parent: Map<number, number> = new Map();
6 private ap: Set<number> = new Set();
7
8 find(graph: Map<number, number[]>): number[] {
9 const visited = new Set<number>();
10
11 for (const v of graph.keys()) {
12 if (!visited.has(v)) {
13 this.dfs(v, graph, visited);
14 }
15 }
16
17 return Array.from(this.ap);
18 }
19
20 private dfs(u: number, graph: Map<number, number[]>, visited: Set<number>): void {
21 visited.add(u);
22 this.disc.set(u, this.time);
23 this.low.set(u, this.time);
24 this.time++;
25
26 let children = 0;
27
28 for (const v of graph.get(u) || []) {
29 if (!visited.has(v)) {
30 children++;
31 this.parent.set(v, u);
32 this.dfs(v, graph, visited);
33
34 this.low.set(u, Math.min(this.low.get(u)!, this.low.get(v)!));
35
36 // Check AP condition
37 if (!this.parent.has(u) && children > 1) {
38 this.ap.add(u); // Root with 2+ children
39 }
40
41 if (this.parent.has(u) && this.low.get(v)! >= this.disc.get(u)!) {
42 this.ap.add(u); // Non-root
43 }
44 } else if (v !== this.parent.get(u)) {
45 this.low.set(u, Math.min(this.low.get(u)!, this.disc.get(v)!));
46 }
47 }
48 }
49}Deep Dive
Theoretical Foundation
Vertex v is articulation point if: 1) v is root with 2+ children in DFS tree, or 2) v has child u where low[u] ≥ disc[v]. low[v] = minimum of disc[v], disc of back-edge ancestors, low of children.
Complexity
Time
O(V+E)
O(V+E)
O(V+E)
Space
O(V)
Applications
Industry Use
Network infrastructure reliability analysis
Social network critical user identification
Transportation system bottleneck detection
Circuit design fault tolerance
Internet backbone vulnerability assessment
Supply chain critical node analysis
Communication network resilience planning
Use Cases
Related Algorithms
Depth-First Search (DFS)
Graph traversal exploring as deep as possible before backtracking. DFS is a fundamental algorithm that uses a stack (either implicitly through recursion or explicitly) to explore graph vertices. It's essential for cycle detection, topological sorting, and pathfinding problems.
Breadth-First Search (BFS)
Level-by-level graph traversal guaranteeing shortest paths in unweighted graphs. BFS uses a queue to explore vertices level by level, making it optimal for finding shortest paths and solving problems that require exploring nearest neighbors first.
Dijkstra's Algorithm
Finds shortest path from source to all vertices in weighted graph with non-negative edges. Uses greedy approach with priority queue.
Floyd-Warshall Algorithm
Floyd-Warshall is an all-pairs shortest path algorithm that finds shortest distances between every pair of vertices in a weighted graph. Unlike Dijkstra (single-source), it computes shortest paths from all vertices to all other vertices simultaneously. The algorithm can handle negative edge weights but not negative cycles. Developed independently by Robert Floyd, Bernard Roy, and Stephen Warshall in the early 1960s.