# 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

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: