Graph AlgosGraph Algorithms

Articulation Points

Find every vertex of an undirected graph whose removal disconnects it, via DFS low-link values with a special rule for the root.

Learn Articulation Points →
ABCDEFG
Articulation points
empty
1/23An articulation point is a node whose removal disconnects the graph. One DFS with discovery times and low-links finds all of them in O(V + E).
Current node (label = disc/low)On recursion pathFinishedDFS tree edgeBack edgeArticulation point
PseudocodeLearn Articulation Points →
1time = 0
2def dfs(u, parent):
3  disc[u] = low[u] = time; time += 1
4  for v in neighbors(u), skipping parent:
5    if v unvisited: dfs(v, u); low[u] = min(low[u], low[v])
6      if parent != None and low[v] >= disc[u]: u is an articulation point
7    else: low[u] = min(low[u], disc[v])   # back edge
8  if parent == None and tree children >= 2: root u is an articulation point
9for u in nodes: if u unvisited: dfs(u, None)
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed