Bridges and Articulation Points in Python, Java and TypeScript

One depth-first search that records discovery times and low values and reports both verdicts as it backs out.

Bridges and articulation points come out of one recursive depth-first search that sets each vertex's discovery time and low value and applies both tests as it returns from each child. The listings below run it on the graph from Bridges and Articulation Points From Discovery Times and Low Values, with edges A-B, B-C, C-A, B-D, D-E, E-B and E-F.

Discovery times, low values, bridges and articulation points from one depth-first search

bridges_code.pypy

def weak_links(graph):
    discovery, low = {}, {}
    bridges, articulation = [], set()

    def visit(vertex, parent):
        discovery[vertex] = low[vertex] = len(discovery)
        children = 0
        for neighbour in graph[vertex]:
            if neighbour == parent:
                continue
            if neighbour in discovery:
                low[vertex] = min(low[vertex], discovery[neighbour])
                continue
            children += 1
            visit(neighbour, vertex)
            low[vertex] = min(low[vertex], low[neighbour])
            if low[neighbour] > discovery[vertex]:
                bridges.append((vertex, neighbour))
            if parent is not None and low[neighbour] >= discovery[vertex]:
                articulation.add(vertex)
        if parent is None and children > 1:
            articulation.add(vertex)

    for vertex in graph:
        if vertex not in discovery:
            visit(vertex, None)
    return discovery, low, bridges, sorted(articulation)


def undirected(edges):
    graph = {}
    for u, v in edges:
        graph.setdefault(u, []).append(v)
        graph.setdefault(v, []).append(u)
    return graph


EDGES = [("A", "B"), ("B", "C"), ("C", "A"), ("B", "D"), ("D", "E"), ("E", "B"), ("E", "F")]

discovery, low, bridges, articulation = weak_links(undirected(EDGES))
for vertex in discovery:
    print(f"{vertex}: discovery {discovery[vertex]}, low {low[vertex]}")
print("bridges:", ", ".join(f"{u}-{v}" for u, v in bridges))
print("articulation points:", ", ".join(articulation))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

A: discovery 0, low 0
B: discovery 1, low 0
C: discovery 2, low 0
D: discovery 3, low 1
E: discovery 4, low 1
F: discovery 5, low 5
bridges: E-F
articulation points: B, E

BridgesCode.javajava

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeSet;

public class BridgesCode {
    private final Map<String, List<String>> graph;
    private final Map<String, Integer> discovery = new LinkedHashMap<>();
    private final Map<String, Integer> low = new LinkedHashMap<>();
    private final List<String> bridges = new ArrayList<>();
    private final TreeSet<String> articulation = new TreeSet<>();

    BridgesCode(Map<String, List<String>> graph) {
        this.graph = graph;
        for (String vertex : graph.keySet()) {
            if (!discovery.containsKey(vertex)) visit(vertex, null);
        }
    }

    private void visit(String vertex, String parent) {
        discovery.put(vertex, discovery.size());
        low.put(vertex, discovery.get(vertex));
        int children = 0;
        for (String neighbour : graph.get(vertex)) {
            if (neighbour.equals(parent)) continue;
            if (discovery.containsKey(neighbour)) {
                low.put(vertex, Math.min(low.get(vertex), discovery.get(neighbour)));
                continue;
            }
            children++;
            visit(neighbour, vertex);
            low.put(vertex, Math.min(low.get(vertex), low.get(neighbour)));
            if (low.get(neighbour) > discovery.get(vertex)) bridges.add(vertex + "-" + neighbour);
            if (parent != null && low.get(neighbour) >= discovery.get(vertex)) articulation.add(vertex);
        }
        if (parent == null && children > 1) articulation.add(vertex);
    }

    static Map<String, List<String>> undirected(String[][] edges) {
        Map<String, List<String>> graph = new LinkedHashMap<>();
        for (String[] edge : edges) {
            graph.computeIfAbsent(edge[0], key -> new ArrayList<>()).add(edge[1]);
            graph.computeIfAbsent(edge[1], key -> new ArrayList<>()).add(edge[0]);
        }
        return graph;
    }

    public static void main(String[] args) {
        String[][] edges = {{"A", "B"}, {"B", "C"}, {"C", "A"}, {"B", "D"}, {"D", "E"}, {"E", "B"}, {"E", "F"}};
        BridgesCode result = new BridgesCode(undirected(edges));
        for (String vertex : result.discovery.keySet()) {
            System.out.println(vertex + ": discovery " + result.discovery.get(vertex) + ", low " + result.low.get(vertex));
        }
        System.out.println("bridges: " + String.join(", ", result.bridges));
        System.out.println("articulation points: " + String.join(", ", result.articulation));
    }
}

OutputRan with eclipse-temurin:25.0.4.1_1-jdk-noble (Java 25.0.4.1)

A: discovery 0, low 0
B: discovery 1, low 0
C: discovery 2, low 0
D: discovery 3, low 1
E: discovery 4, low 1
F: discovery 5, low 5
bridges: E-F
articulation points: B, E

bridges_code.tsts

function weakLinks(graph: Map<string, string[]>): { discovery: Map<string, number>; low: Map<string, number>; bridges: string[]; articulation: string[] } {
  const discovery = new Map<string, number>();
  const low = new Map<string, number>();
  const bridges: string[] = [];
  const articulation = new Set<string>();

  function visit(vertex: string, parent: string | null): void {
    discovery.set(vertex, discovery.size);
    low.set(vertex, discovery.get(vertex)!);
    let children = 0;
    for (const neighbour of graph.get(vertex)!) {
      if (neighbour === parent) continue;
      if (discovery.has(neighbour)) {
        low.set(vertex, Math.min(low.get(vertex)!, discovery.get(neighbour)!));
        continue;
      }
      children++;
      visit(neighbour, vertex);
      low.set(vertex, Math.min(low.get(vertex)!, low.get(neighbour)!));
      if (low.get(neighbour)! > discovery.get(vertex)!) bridges.push(`${vertex}-${neighbour}`);
      if (parent !== null && low.get(neighbour)! >= discovery.get(vertex)!) articulation.add(vertex);
    }
    if (parent === null && children > 1) articulation.add(vertex);
  }

  for (const vertex of graph.keys()) {
    if (!discovery.has(vertex)) visit(vertex, null);
  }
  return { discovery, low, bridges, articulation: [...articulation].sort() };
}

function undirected(edges: [string, string][]): Map<string, string[]> {
  const graph = new Map<string, string[]>();
  for (const [u, v] of edges) {
    if (!graph.has(u)) graph.set(u, []);
    if (!graph.has(v)) graph.set(v, []);
    graph.get(u)!.push(v);
    graph.get(v)!.push(u);
  }
  return graph;
}

const edges: [string, string][] = [["A", "B"], ["B", "C"], ["C", "A"], ["B", "D"], ["D", "E"], ["E", "B"], ["E", "F"]];
const { discovery, low, bridges, articulation } = weakLinks(undirected(edges));
for (const [vertex, time] of discovery) console.log(`${vertex}: discovery ${time}, low ${low.get(vertex)}`);
console.log(`bridges: ${bridges.join(", ")}`);
console.log(`articulation points: ${articulation.join(", ")}`);

OutputRan with node:24.22.0-trixie-slim (Node 24.22.0), TypeScript 5.9.3

A: discovery 0, low 0
B: discovery 1, low 0
C: discovery 2, low 0
D: discovery 3, low 1
E: discovery 4, low 1
F: discovery 5, low 5
bridges: E-F
articulation points: B, E

All three printed the same lines, and they match the table on the concept card. The highlighted lines are the three decisions the search makes. The first skips the edge back to the parent: in an undirected graph every tree edge appears in both neighbour lists, and without the skip the child would count its own parent as a back edge, give itself the parent's discovery time as its low value, and no edge would ever be a bridge. The second is the bridge test, low[child] > disc[parent], and the third the articulation test, low[child] ≥ disc[parent], which the root is excused from. The root is judged after its loop instead, by counting its children in the tree.

Skipping by the parent's name assumes at most one edge joins two vertices. With two parallel edges between the same pair, the second is a genuine way round, and a version that must allow them skips the parent edge by its index rather than by the vertex at its end.

Bridges are found on the way back up, so a graph with several lists them deepest first. Python and TypeScript keep articulation points in a set and sort them at the end; Java keeps them in a TreeSet, which stays sorted. The search is recursive, one call per vertex on the current path, which is fine at seven vertices. A path of thousands of vertices passes Python's default recursion limit of 1000 and can overflow a Java or JavaScript call stack, so code for large graphs keeps its own stack of vertices and neighbour positions and applies the two tests when it pops a child. Either form runs in O(V + E) time and O(V) extra space.

← → move through sections and cards