AlgoVerse

Articulation points

Find the nodes whose removal splits the graph, with one DFS and each node's low value (the earliest discovery time reachable from its subtree).

An articulation point (cut vertex) is a node whose removal disconnects the graph. Trying to remove each node in turn costs O(V·(V + E)); one DFS is enough:

Read the full explanation ↓
Input:
V=7 · E=8 · src=APDF export

Two triangles joined by the bridge D — E; D and E are articulation points.

  1. def articulation_points(graph, src):
  2. disc = {v: 0 for v in graph}
  3. low = {v: 0 for v in graph}
  4. cut = set()
  5. timer = [0]
  6. for s in graph:
  7. if disc[s] == 0:
  8. visit(graph, s, None, disc, low, cut, timer)
  9. return cut
  12. def visit(graph, u, parent, disc, low, cut, timer):
  13. timer[0] = timer[0] + 1
  14. disc[u] = timer[0]
  15. low[u] = timer[0]
  16. children = 0
  17. for v, _ in graph[u]:
  18. if disc[v] == 0:
  19. children = children + 1
  20. visit(graph, v, u, disc, low, cut, timer)
  21. low[u] = min(low[u], low[v])
  22. if parent is not None:
  23. if low[v] >= disc[u]:
  24. cut.add(u)
  25. elif v != parent:
  26. low[u] = min(low[u], disc[v])
  27. if parent is None:
  28. if children > 1:
  29. cut.add(u)

Invariant: low[u] is the smallest disc reachable from u's subtree using at most one back edge.

Start

ABCDEFG
  • Current node (u)
  • Search tree (from parent)
  • Edge being checked

Recursion tree

Filled orange = running call · Orange outline = still on the stack · Grey = finished

Local variables

src'A'

Orange = changed in this step

graph dict
  • 'A': [('B', 1), ('D', 1)]
  • 'B': [('A', 1), ('D', 1)]
  • 'C': [('D', 1)]
  • 'D': [('B', 1), ('A', 1), ('E', 1), ('C', 1)]
  • 'E': [('D', 1), ('F', 1), ('G', 1)]
  • 'F': [('E', 1), ('G', 1)]
  • 'G': [('F', 1), ('E', 1)]

Call stack

  1. articulation_points()line 1
Step 1 of 150
Black = discover · Orange = key stepdiscover: 0/7 · check: 0/16 · back_edge: 0/4 · pull_low: 0/6 · test: 0/5 · cut_vertex: 0/3 · root_test: 0/1 · tree_done: 0/1

    How the work grows with input size

    Average of 5 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • check
    • current input (n=7)
    050100481216202428n = number of nodescheck
    Show as a table
    ncheck
    410.4
    827.6
    1241.6
    1656
    2070.8
    2474.4
    2894.4
    Explanation

    The idea

    An articulation point (cut vertex) is a node whose removal disconnects the graph. Trying to remove each node in turn costs O(V·(V + E)); one DFS is enough:

    • disc[u]: the time u was discovered.
    • low[u]: the earliest discovery time reachable from u's subtree (through tree edges and at most one back edge).

    The rule

    • A non-root node u is an articulation point if it has a child v with low[v] ≥ disc[u]: the subtree of v cannot reach above u without going through u.
    • The root is an articulation point if it has more than one child in the DFS tree.

    Cost

    One DFS: O(V + E).

    What to watch in the trace

    • The number next to each node is its low; watch back edges pull it down.
    • The cut set in the memory panel holds the articulation points found so far.