articulation point or cut vertex in graph
Articulation point or cut vertex in graph is a vertex of a graph where if we remove this vertex, the graph becomes disconnected. For example the below graph becomes disconnected if we remove the vertex 3. For more about connected graph visit http://wikistack.com/check-whether-a-given-graph-is-connected-or-not/.
In the above figure 3 is articulation point or cut vertex. The disconnected graph means there is at least one pair of vertices in the remaining graph (after removal of cut vertex 3) that would be unreachable. Ex. after removing cut vertex 3, the nodes 1 and 5 are unreachable from each other. Same as 2 and 4 are also unreachable.
A graph may contain no articulation point or cut vertex in graph
How to find articulation point
The easiest way to find articulation point is remove each vertex one by one and check whether the resulting graph is still connected or not. If we apply this approach on the graph represented as adjacency list then the complexity would be O(V*(V+E)).
From fig. 1.1 it is clear that after removing any node we have to adjust adjacency list the resulting graph and test the connectivity of resulting graph.
Finding articulation point or cut vertex using depth first search (DFS)
- Apply DFS on a graph to find DFS tree.
- A node which is visited earlier is a “parent” of those nodes which are reached by it and visited later.
- If any child of a node does not have a path to any of the ancestors of its parent, it means that removing this node would make this child disjoint from the graph.
- The root of the tree is special case. If it has more than one child, then it is an articulation point or cut vertex, otherwise not.