Find articulation points or cut vertices in a graph

graph-algorithm
depth-first-search
articulation-points
cut-vertices

(Team) #1
A vertex in an undirected connected graph is an articulation point or cut vertex if and only if removing it, and the edges connected to it, splits the graph into multiple components.

Depth First Search can be used to find cut vertices.

The average case time complexity is O(V+E) and the auxiliary space complexity is O(V)

Refer the article for more details and implementations.

Share your thoughts or ask any questions below.
This is a companion discussion topic for the original entry at http://iq.opengenus.org/find-articulation-points-or-cut-vertices-in-a-graph/