Articulation points (low-link DFS): Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Treat each input edge as undirected. Skip only the parent edge, preserving parallel edges; compare discovery times and low links.

A non-root is a cut vertex when a child subtree cannot bypass it to a strict ancestor; a root requires multiple DFS children.

Open the 3D visualization

Articulation points (low-link DFS) example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Articulation points (low-link DFS)

Finding single-vertex undirected network vulnerabilities.

Choosing an alternative

Bridges identify fragile edges rather than vertices.

Worked example: input and state changes

Example input

0,1,1;1,2,1;2,0,1;2,3,1;3,4,1;4,3,1

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: Initialize graph state.

    State at this checkpoint
    {
      "values": [
        "-",
        "-",
        "-",
        "-",
        "-"
      ],
      "active": [],
      "kind": "graph",
      "chosen": [],
      "visited": []
    }
  2. Step 4: Inspect non-parent edge #2; update low[2]=0.

    State at this checkpoint
    {
      "values": [
        "d:0 l:0",
        "d:1 l:1",
        "d:2 l:0",
        "d:-1 l:-1",
        "d:-1 l:-1"
      ],
      "active": [
        2,
        0
      ],
      "kind": "graph",
      "chosen": [],
      "visited": [],
      "discovery": [
        0,
        1,
        2,
        -1,
        -1
      ],
      "low": [
        0,
        1,
        0,
        -1,
        -1
      ],
      "bridgeEdges": [],
      "cutVertices": []
    }
  3. Step 7: Inspect non-parent edge #5; update low[4]=3.

    State at this checkpoint
    {
      "values": [
        "d:0 l:0",
        "d:1 l:1",
        "d:2 l:0",
        "d:3 l:3",
        "d:4 l:3"
      ],
      "active": [
        4,
        3
      ],
      "kind": "graph",
      "chosen": [],
      "visited": [],
      "discovery": [
        0,
        1,
        2,
        3,
        4
      ],
      "low": [
        0,
        1,
        0,
        3,
        3
      ],
      "bridgeEdges": [],
      "cutVertices": []
    }
  4. Step 11: Return 2 > 1; low[2]=0, discovery[1]=1.

    State at this checkpoint
    {
      "values": [
        "d:0 l:0",
        "d:1 l:0",
        "d:2 l:0 cut",
        "d:3 l:3 cut",
        "d:4 l:3"
      ],
      "active": [
        1,
        2
      ],
      "kind": "graph",
      "chosen": [
        3
      ],
      "visited": [],
      "discovery": [
        0,
        1,
        2,
        3,
        4
      ],
      "low": [
        0,
        0,
        0,
        3,
        3
      ],
      "bridgeEdges": [
        3
      ],
      "cutVertices": [
        2,
        3
      ]
    }
  5. Step 14: Articulation vertices: 2, 3.

    State at this checkpoint
    {
      "values": [
        "d:0 l:0",
        "d:1 l:0",
        "d:2 l:0 cut",
        "d:3 l:3 cut",
        "d:4 l:3"
      ],
      "active": [],
      "kind": "graph",
      "chosen": [
        3
      ],
      "visited": [
        2,
        3
      ],
      "result": 2,
      "bridgeEdges": [
        3
      ],
      "cutVertices": [
        2,
        3
      ],
      "discovery": [
        0,
        1,
        2,
        3,
        4
      ],
      "low": [
        0,
        0,
        0,
        3,
        3
      ]
    }

Expected final state

Articulation vertices: 2, 3.

Complexity and input bounds

Family: Graphs. Time complexity: O(V + VE) with edge-array scans.

Space complexity: O(V) discovery, low-link, and cut flags.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

Directed edges as source,target,weight; separated by semicolons. Nodes 0–7, positive weights 1–99. Start node is 0. At most 16 edges. Weights are ignored. Edges are undirected; duplicate edges are distinct.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

The root rule differs from the non-root rule and must be applied separately in every component.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// Edge arrays from/to/weight; 1..8 vertices indexed 0..vertices-1, 0..16 edges, endpoints in bounds. Weights ignored. Output buffer at least 256 integers. Treat edges as undirected; parallel edges are distinct. Returns count and writes one 0/1 articulation flag per vertex. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(from, to, weight, edges, vertices, output) {
    let disc = Array(256).fill(0); let low = Array(256).fill(0); let parent = Array(256).fill(0); let parentEdge = Array(256).fill(0); let cursor = Array(256).fill(0); let children = Array(256).fill(0); let dfs = Array(256).fill(0); let cut = Array(256).fill(0); let bridge = Array(256).fill(0);
    let root = 0; let u = 0; let v = 0; let index = 0; let top = 0; let clock = 0; let count = 0;
    for (u = 0; u < vertices; u++) { disc[u] = -1; parent[u] = -1; parentEdge[u] = -1; }
    for (root = 0; root < vertices; root++) {
        if (disc[root] >= 0) { continue; }
        disc[root] = clock; low[root] = clock++; dfs[top++] = root;
        while (top > 0) {
            u = dfs[top - 1]; index = cursor[u];
            while (index < edges && (index == parentEdge[u] || (from[index] != u && to[index] != u))) { index++; }
            cursor[u] = index + 1;
            if (index < edges) {
                v = from[index]; if (v == u) { v = to[index]; }
                if (disc[v] < 0) { parent[v] = u; parentEdge[v] = index; children[u]++; disc[v] = clock; low[v] = clock++; dfs[top++] = v; }
                else if (disc[v] < low[u]) { low[u] = disc[v]; }
            } else {
                top--; v = parent[u];
                if (v < 0) { if (children[u] > 1) { cut[u] = 1; } }
                else {
                    if (low[u] < low[v]) { low[v] = low[u]; }
                    if (low[u] > disc[v]) { bridge[parentEdge[u]] = 1; }
                    if (parent[v] >= 0 && low[u] >= disc[v]) { cut[v] = 1; }
                }
            }
        }
    }
    for (index = 0; index < vertices; index++) { output[index] = cut[index]; count += output[index]; }
    return count;
}

Source

Primary research source for the algorithm or its underlying method. The playground is a bounded teaching implementation, not the publication's original program.