Articulation Points Graph Algorithm using torjan’s algorithm (Cut Vertices)

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.

eecs wsu PDF

Video

Cut Vertex

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]
Author: Hrishikesh Mishra