Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Python articulation points: find vertices that separate an undirected graph

Last updated: 30 Sept 20264 min read
tutorial
IntermediateBy AITrove Editorial

An articulation point is a vertex whose removal increases the connected-component count of an undirected graph.

Download Python source kit

Operation contract

The traversal records discovery order and the earliest reachable ancestor for each subtree. A non-root vertex separates a child subtree when that child cannot reach an earlier ancestor. A DFS root follows a different rule: it separates components only when it has more than one traversal child. Each edge has its own ID so skipping the incoming edge does not discard a second parallel edge. Self-loops do not create an extra DFS child.

Failure and ownership boundary

The graph is an owned undirected edge list with 0 to 32 numbered vertices and at most 128 edges. It accepts parallel edges and self-loops, rejects Boolean endpoints and validates before building adjacency. Do not apply the undirected parent-edge rule to directed reachability. Compare Python graph bridges: track edge identity when parallel links are allowed, Python strongly connected components: partition a directed dependency graph and Python union-find: connected groups with path compression.

Working program

python
def articulation_points(vertex_count, edges):
    if type(vertex_count) is not int or not 0 <= vertex_count <= 32 or type(edges) is not list or len(edges) > 128:
        raise ValueError("bounded graph required")
    adjacency = [[] for _ in range(vertex_count)]
    for edge_id, pair in enumerate(edges):
        if type(pair) is not tuple or len(pair) != 2 or any(type(vertex) is not int or not 0 <= vertex < vertex_count for vertex in pair):
            raise ValueError("valid endpoints required")
        left, right = pair
        adjacency[left].append((right, edge_id))
        adjacency[right].append((left, edge_id))
    discovered, low = [-1] * vertex_count, [0] * vertex_count
    clock, separating = 0, set()
    def visit(vertex, incoming):
        nonlocal clock
        discovered[vertex] = low[vertex] = clock
        clock += 1
        children = 0
        for neighbor, edge_id in adjacency[vertex]:
            if edge_id == incoming:
                continue
            if discovered[neighbor] == -1:
                children += 1
                visit(neighbor, edge_id)
                low[vertex] = min(low[vertex], low[neighbor])
                if incoming is not None and low[neighbor] >= discovered[vertex]:
                    separating.add(vertex)
            else:
                low[vertex] = min(low[vertex], discovered[neighbor])
        if incoming is None and children > 1:
            separating.add(vertex)
    for vertex in range(vertex_count):
        if discovered[vertex] == -1:
            visit(vertex, None)
    return sorted(separating)

print("separating:", articulation_points(5, [(0, 1), (1, 2), (2, 0), (1, 3), (3, 4), (1, 3)]))
print("cycle:", articulation_points(3, [(0, 1), (1, 2), (2, 0)]))

Output

Output
separating: [1, 3]
cycle: []

Costs and limits

Traversal and adjacency storage take O(V + E), followed by O(A log A) sorting for A returned vertices. The recursion depth is bounded by the accepted 32 vertices. Larger graphs should use an explicit traversal stack or a separately tested depth policy.

Common Mistakes

  • The DFS root needs the child-count rule.
  • Skip an incoming edge ID, not every edge to the parent vertex.

Connected lessons

Python graph bridges: track edge identity when parallel links are allowed, Python strongly connected components: partition a directed dependency graph, Python recursion: bound depth instead of raising the limit.

python
articulation-points
Storage details