Understanding the Problem
We are given an undirected graph. Our goal is to find all the articulation points in this graph. An articulation point (or cut vertex) is a node that, if removed, increases the number of connected components in the graph.
In simple terms, these are the critical nodes that hold parts of the graph together. If any of them are removed, some nodes may no longer be reachable from others.
This is especially useful in network design and fault-tolerant systems where you want to identify single points of failure.
Step-by-Step Solution with Example
step 1: Represent the graph
We begin by representing the graph using an adjacency list. For example, let's take this graph:
{
0: [1, 2],
1: [0, 2],
2: [0, 1, 3, 5],
3: [2, 4],
4: [3],
5: [2, 6, 8],
6: [5, 7],
7: [6],
8: [5]
}
This graph has 9 nodes (0 to 8), and is connected in such a way that removing some nodes would disconnect parts of it.
step 2: Perform DFS traversal and track timestamps
We use Depth-First Search (DFS) to explore the graph and keep track of:
tin[u]
: The discovery time of node u
low[u]
: The lowest discovery time reachable from u
or any of its descendants
We initialize both of these arrays with -1
and use a global timer
to assign timestamps as we go.
step 3: Apply articulation point conditions during DFS
While traversing each node u
, we apply the following logic:
- Case 1 (Root): If
u
is the root of DFS and has more than one child, then u
is an articulation point.
- Case 2 (Bridge): If
u
is not root and there exists a child v
such that low[v] >= tin[u]
, then u
is an articulation point.
step 4: Update low values properly
After visiting a neighbor v
of u
, we update low[u]
based on:
- If
v
is a child: low[u] = min(low[u], low[v])
- If
v
is already visited and is not parent of u
: low[u] = min(low[u], tin[v])
step 5: Collect all articulation points
We use a boolean array isArticulation[u]
to mark nodes that satisfy the above conditions. After DFS is complete, we collect all nodes marked as articulation points.
Edge Cases
- Single Node: A graph with only one node has no articulation points.
- Disconnected Graph: Apply DFS from every unvisited node to ensure all components are covered.
- Tree Graph: In a tree, all non-leaf nodes (except the root with one child) can be articulation points.
- Cyclic Graph: Presence of back edges affects the
low
values and prevents over-marking articulation points.
Finally
The key to solving this problem is understanding how DFS works in combination with discovery and low times. By tracking when we visit a node and the lowest point reachable from it, we can detect where the graph would split if a node is removed.
This method is efficient (O(V + E)) and elegant, using classic DFS with a few smart checks to find critical points in any connected or disconnected undirected graph.
Comments
Loading comments...