Articulation Points Graph Algorithm using torjan’s algorithm Cut Vertices
Facts:
- Root is articulation point iff it has more than one child
- Any other vertex v is an articulation point iff v has some child w such that Low(w) ≥ Num(v)
-
- I.e., is there a child w of v that cannot reach a vertex visited before v?
- If yes, then removing v will disconnect w (and v is an articulation point)
- Can compute Num(v) and Low(v) in O(|E|+|V|) time
Algorithm:
- From any vertex v, perform DFS and number vertice as they are visited
- Num(v) is the visit number
- Let Low(v) = lowest-numbered vertex reachable from v using 0 or more spanning tree edges and then at most one back edge
-
- Low(v) = minimum of
- Num(v)
- Lowest Num(w) among all back edges (v,w)
- Lowest Low(w) among all tree edges (v,w)
- Apply DFS on a graph. Get the 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.
- There is an exception: the root of the tree. If it has more than one child, then it is an articulation point, otherwise not.
Latest Source Code:
Github: GraphCutVertices.java
Output:
- T - - - - - T - T T - - - - T - - T - - - T - - T T T - - T T - - - - - - T - - T - - - T - T - Articulation Points: [3, 1]