AlgoScope

Bridges and Components

One depth-first search, decorated with two numbers per vertex, answers every question about how a graph holds together. The discovery time says when a vertex was entered. The low-link says how far back up the search tree it can climb using its subtree and a single back edge. If a child cannot climb above its parent, the edge between them is a bridge. If it cannot climb past the parent, the parent is an articulation point. In a directed graph the same low-link finds strongly connected components: a vertex whose low-link is its own discovery time closes a component, and Tarjan pops it off the stack in one go. Kosaraju reaches the same components with two ordinary searches, the second on the reversed graph, taking start vertices in order of latest finish first.

The player

Finding bridges over 7 vertices.0123456

Find the bridges of this graph with one DFS. Each vertex gets a discovery time, its position in the order label, and a low-link, the badge: the earliest discovery time it can reach by walking down tree edges and then along a single back edge. A tree edge u-v is a bridge when v cannot climb above u at all, low[v] > disc[u].

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 10, with their answers.

  1. Edge 2-0 reaches an already seen vertex with disc[0] = 0, and low[2] = 2. What happens?

    • low[2] becomes 0
    • Nothing, low[2] stays 2
    • 0 is entered again

    Answer: low[2] becomes 0. A back edge lowers low[u] to disc[w] when that is earlier. A seen vertex is never entered twice.

  2. Edge 5-3 reaches an already seen vertex with disc[3] = 3, and low[5] = 5. What happens?

    • low[5] becomes 3
    • Nothing, low[5] stays 5
    • 3 is entered again

    Answer: low[5] becomes 3. A back edge lowers low[u] to disc[w] when that is earlier. A seen vertex is never entered twice.

  3. dfs(6) returned with low[6] = 6 and disc[5] = 5. Is 5-6 a bridge?

    • Yes, low[6] > disc[5]
    • No, low[6] <= disc[5]

    Answer: Yes, low[6] > disc[5]. A bridge is a tree edge whose lower end cannot reach the upper end by any other route.

  4. dfs(5) returned with low[5] = 3 and disc[4] = 4. Is 4-5 a bridge?

    • Yes, low[5] > disc[4]
    • No, low[5] <= disc[4]

    Answer: No, low[5] <= disc[4]. A bridge is a tree edge whose lower end cannot reach the upper end by any other route.

  5. dfs(4) returned with low[4] = 3 and disc[3] = 3. Is 3-4 a bridge?

    • Yes, low[4] > disc[3]
    • No, low[4] <= disc[3]

    Answer: No, low[4] <= disc[3]. A bridge is a tree edge whose lower end cannot reach the upper end by any other route.

  6. Edge 3-5 reaches an already seen vertex with disc[5] = 5, and low[3] = 3. What happens?

    • low[3] becomes 5
    • Nothing, low[3] stays 3
    • 5 is entered again

    Answer: Nothing, low[3] stays 3. A back edge lowers low[u] to disc[w] when that is earlier. A seen vertex is never entered twice.

  7. dfs(3) returned with low[3] = 3 and disc[2] = 2. Is 2-3 a bridge?

    • Yes, low[3] > disc[2]
    • No, low[3] <= disc[2]

    Answer: Yes, low[3] > disc[2]. A bridge is a tree edge whose lower end cannot reach the upper end by any other route.

  8. dfs(2) returned with low[2] = 0 and disc[1] = 1. Is 1-2 a bridge?

    • Yes, low[2] > disc[1]
    • No, low[2] <= disc[1]

    Answer: No, low[2] <= disc[1]. A bridge is a tree edge whose lower end cannot reach the upper end by any other route.

  9. dfs(1) returned with low[1] = 0 and disc[0] = 0. Is 0-1 a bridge?

    • Yes, low[1] > disc[0]
    • No, low[1] <= disc[0]

    Answer: No, low[1] <= disc[0]. A bridge is a tree edge whose lower end cannot reach the upper end by any other route.

  10. Edge 0-2 reaches an already seen vertex with disc[2] = 2, and low[0] = 0. What happens?

    • low[0] becomes 2
    • Nothing, low[0] stays 0
    • 2 is entered again

    Answer: Nothing, low[0] stays 0. A back edge lowers low[u] to disc[w] when that is earlier. A seen vertex is never entered twice.

How it runs, step by step

  1. Find the bridges of this graph with one DFS. Each vertex gets a discovery time, its position in the order label, and a low-link, the badge: the earliest discovery time it can reach by walking down tree edges and then along a single back edge. A tree edge u-v is a bridge when v cannot climb above u at all, low[v] > disc[u].

    Finding bridges over 7 vertices.

  2. Enter 0 at time 0: disc[0] = low[0] = 0. Until a back edge or a child says otherwise, the earliest vertex 0 can reach is itself.

    Enter 0, discovery time 0.

  3. Enter 1 at time 1: disc[1] = low[1] = 1. Until a back edge or a child says otherwise, the earliest vertex 1 can reach is itself.

    Enter 1, discovery time 1.

  4. Enter 2 at time 2: disc[2] = low[2] = 2. Until a back edge or a child says otherwise, the earliest vertex 2 can reach is itself.

    Enter 2, discovery time 2.

  5. Edge 2-0 leads to a vertex seen at time 0, an ancestor on the current path. That is earlier than low[2] = 2, so low[2] becomes 0: 2 can climb to 0.

    Back edge 2 to 0, low of 2 is 0.

  6. Enter 3 at time 3: disc[3] = low[3] = 3. Until a back edge or a child says otherwise, the earliest vertex 3 can reach is itself.

    Enter 3, discovery time 3.

  7. Enter 4 at time 4: disc[4] = low[4] = 4. Until a back edge or a child says otherwise, the earliest vertex 4 can reach is itself.

    Enter 4, discovery time 4.

  8. Enter 5 at time 5: disc[5] = low[5] = 5. Until a back edge or a child says otherwise, the earliest vertex 5 can reach is itself.

    Enter 5, discovery time 5.

  9. Edge 5-3 leads to a vertex seen at time 3, an ancestor on the current path. That is earlier than low[5] = 5, so low[5] becomes 3: 5 can climb to 3.

    Back edge 5 to 3, low of 5 is 3.

  10. Enter 6 at time 6: disc[6] = low[6] = 6. Until a back edge or a child says otherwise, the earliest vertex 6 can reach is itself.

    Enter 6, discovery time 6.

  11. dfs(6) returned with low[6] = 6. low[5] stays 3. low[6] = 6 > disc[5] = 5: nothing below 6 reaches 5 or above, so 5-6 is a bridge.

    Back in 5, low 3.

  12. dfs(5) returned with low[5] = 3. low[4] drops to 3. low[5] = 3 <= disc[4] = 4: a back edge below 5 reaches 4 or higher, so 4-5 lies on a cycle.

    Back in 4, low 3.

  13. dfs(4) returned with low[4] = 3. low[3] stays 3. low[4] = 3 <= disc[3] = 3: a back edge below 4 reaches 3 or higher, so 3-4 lies on a cycle.

    Back in 3, low 3.

  14. Edge 3-5 leads to a vertex seen at time 5, already finished. low[3] = 3 is already that early or earlier, so nothing changes.

    Back edge 3 to 5, low of 3 is 3.

  15. dfs(3) returned with low[3] = 3. low[2] stays 0. low[3] = 3 > disc[2] = 2: nothing below 3 reaches 2 or above, so 2-3 is a bridge.

    Back in 2, low 0.

  16. dfs(2) returned with low[2] = 0. low[1] drops to 0. low[2] = 0 <= disc[1] = 1: a back edge below 2 reaches 1 or higher, so 1-2 lies on a cycle.

    Back in 1, low 0.

  17. dfs(1) returned with low[1] = 0. low[0] stays 0. low[1] = 0 <= disc[0] = 0: a back edge below 1 reaches 0 or higher, so 0-1 lies on a cycle.

    Back in 0, low 0.

  18. Edge 0-2 leads to a vertex seen at time 2, already finished. low[0] = 0 is already that early or earlier, so nothing changes.

    Back edge 0 to 2, low of 0 is 0.

  19. Bridges: 5-6, 2-3. Each is the only route between its two sides. every other edge lies on a cycle. Found by one DFS, O(V + E).

    2 bridges.

The code

Bridges and Components, in Python

def dfs(u, parent):                                           # undirected: disc and low per vertex
    global time, children
    disc[u] = time; low[u] = time; time += 1
    for v in adj[u]:
        if disc[v] < 0:                                       # tree edge
            dfs(v, u)
            low[u] = min(low[u], low[v])
            if low[v] > disc[u]: bridges.append((u, v))       # v cannot climb above u: a bridge
            if low[v] >= disc[u] and parent >= 0: cut.add(u)  # v cannot climb past u: a cut vertex
            if parent < 0:
                children += 1
                if children >= 2: cut.add(u)                  # the root cuts when it has two subtrees
        elif v != parent: low[u] = min(low[u], disc[v])       # back edge: u reaches an ancestor

def tarjan(u):                                                # directed: components in one DFS
    global time, count
    disc[u] = time; low[u] = time; time += 1; stack.append(u)
    for v in adj[u]:
        if disc[v] < 0: tarjan(v); low[u] = min(low[u], low[v])
        elif v in stack: low[u] = min(low[u], disc[v])        # v is still open: same component
    if low[u] == disc[u]:                                     # u is the root of its component
        while True:
            w = stack.pop(); component[w] = count
            if w == u: break
        count += 1

def kosaraju():
    global count
    for s in range(n):                                        # pass 1: record finish order
        if not seen[s]: dfs_finish(s)
    reversed_adj = reverse(adj)                               # flip every edge
    for s in reversed(finish):
        if component[s] < 0: dfs_assign(reversed_adj, s, count); count += 1
    return count                                              # pass 2: latest finish first

Bridges and Components, in JavaScript

function dfs(u, parent) {                                       // undirected: disc and low per vertex
  disc[u] = time; low[u] = time; time++;
  for (const v of adj[u]) {
    if (disc[v] < 0) {                                          // tree edge
      dfs(v, u);
      low[u] = Math.min(low[u], low[v]);
      if (low[v] > disc[u]) bridges.push([u, v]);               // v cannot climb above u: a bridge
      if (low[v] >= disc[u] && parent >= 0) cut.add(u);         // v cannot climb past u: a cut vertex
      if (parent < 0 && ++children >= 2) cut.add(u);            // the root cuts when it has two subtrees
    } else if (v !== parent) low[u] = Math.min(low[u], disc[v]);  // back edge: u reaches an ancestor
  }
}

function tarjan(u) {                                            // directed: components in one DFS
  disc[u] = time; low[u] = time; time++; stack.push(u);
  for (const v of adj[u]) {
    if (disc[v] < 0) { tarjan(v); low[u] = Math.min(low[u], low[v]); }
    else if (stack.includes(v)) low[u] = Math.min(low[u], disc[v]);  // v is still open: same component
  }
  if (low[u] === disc[u]) {                                     // u is the root of its component
    let w; do { w = stack.pop(); component[w] = count; } while (w !== u);
    count++;
  }
}

function kosaraju() {
  for (let s = 0; s < n; s++) if (!seen[s]) dfsFinish(s);       // pass 1: record finish order
  const reversed = reverse(adj);                                // flip every edge
  for (const s of [...finish].reverse()) if (component[s] < 0) dfsAssign(reversed, s, count++);
  return count;                                                 // pass 2: latest finish first
}

Bridges and Components, in Kotlin

fun dfs(u: Int, parent: Int) {                                // undirected: disc and low per vertex
    disc[u] = time; low[u] = time; time++
    for (v in adj[u]) {
        if (disc[v] < 0) {                                    // tree edge
            dfs(v, u)
            low[u] = min(low[u], low[v])
            if (low[v] > disc[u]) bridges += u to v            // v cannot climb above u: a bridge
            if (low[v] >= disc[u] && parent >= 0) cut += u     // v cannot climb past u: a cut vertex
            if (parent < 0 && ++children >= 2) cut += u        // the root cuts when it has two subtrees
        } else if (v != parent) low[u] = min(low[u], disc[v]) // back edge: u reaches an ancestor
    }
}

fun tarjan(u: Int) {                                          // directed: components in one DFS
    disc[u] = time; low[u] = time; time++; stack.push(u)
    for (v in adj[u]) {
        if (disc[v] < 0) { tarjan(v); low[u] = min(low[u], low[v]) }
        else if (v in stack) low[u] = min(low[u], disc[v])    // v is still open: same component
    }
    if (low[u] == disc[u]) {                                  // u is the root of its component
        do { val w = stack.pop(); component[w] = count } while (w != u)
        count++
    }
}

fun kosaraju(): Int {
    for (s in 0 until n) if (!seen[s]) dfsFinish(s)           // pass 1: record finish order
    val reversed = reverse(adj)                               // flip every edge
    for (s in finish.reversed()) if (component[s] < 0) dfsAssign(reversed, s, count++)
    return count                                              // pass 2: latest finish first
}

This lesson has no write-it-yourself editor. It is free, like every lesson, and nothing here is locked.

Remember

  • low[u] is the earliest discovery time reachable from u's subtree plus one back edge. A tree edge u-v is a bridge when low[v] > disc[u].
  • Tarjan: push on entry, pop a whole component when a vertex finishes with low[u] == disc[u]. Only vertices still on the stack can lower low.
  • Kosaraju: finish order from one DFS, reverse all edges, then DFS from the latest finisher. Each search paints exactly one component.

Where this is used

Routing engines checking a road networkMapping

One-way streets make a road graph directed, so useful connectivity means mutual reachability: a mistagged one-way can create a pocket a car can drive into and never drive out of, and a plain reachability check will not notice. OSRM runs Tarjan over the extracted graph (util::TarjanSCC) and ships an osrm-components tool that writes the small components, the ones under a thousand nodes, out as GeoJSON so mappers can see the islands. A continent-sized graph would overflow the call stack, so that implementation walks the search with its own explicit stack of frames instead of recursing.

LLVM's bottom-up call graph passesCompilers

llvm/ADT/SCCIterator.h finds the strongly connected components of the call graph with Tarjan and hands them out callees first, which is the order the inliner wants: the cost and behaviour of a function are settled before any caller is looked at. Components rather than a plain topological order are needed because mutually recursive functions cannot be put in an order at all, so they arrive as one unit and are optimised together.

Terraform reporting a dependency cycleDeveloper tools

Terraform decides what to create first by topologically sorting a resource dependency graph, which only has an order if it is acyclic. Its dag package runs Tarjan (StronglyConnected in internal/dag/tarjan.go) and any component holding more than one resource is a loop it cannot order, which is what the Cycle: error lists. Printing the whole component rather than one offending edge is the point - you have to see every member of the loop to know where to break it.

Finding single points of failureNetworking

A bridge is a link with no alternate path and an articulation point is a device whose loss splits the network, which is exactly the list you want before deciding where to spend on redundancy. The obvious method is to delete each link and re-run a reachability check, one traversal per link. The low-link DFS returns every such link and device in a single O(V + E) pass. NetworkX exposes them as bridges() and articulation_points(). The Boost Graph Library has articulation_points() and biconnected_components(), where a bridge is a biconnected component holding a single edge.

Why it works this way

Why a bridge needs low[v] > disc[u] but a cut vertex only needs >=

low[v] > disc[u] says v's subtree cannot reach u at all except through the tree edge, so removing that edge strands the subtree: it is a bridge. low[v] == disc[u] says the subtree can climb back to u but no higher, so the edge lies on a cycle through u and is not a bridge, yet deleting u itself still strands the subtree. Two triangles glued at a single shared vertex are the clean example: the shared vertex is an articulation point and not one edge in the graph is a bridge.

Skipping the parent by vertex id breaks on parallel edges

Every non-tree edge in an undirected DFS points at an ancestor, so the edge back to the parent has to be ignored - otherwise every vertex trivially reaches its parent and nothing ever looks like a bridge. But v != parent skips every edge to the parent, including a second, genuine u-v edge, so the pair gets reported as a bridge even though cutting either copy leaves the graph connected. Skip the one edge you arrived on by its edge id, not by the vertex it leads to.

Tarjan: why an already-seen vertex only counts while it is still on the stack

In a directed graph a visited neighbour v may belong to a component that has already been popped and closed. If v could still reach back to u then u and v would be in the same component, and that component could not have been closed while u is open - so a popped v has no path back to u, and folding its disc into low[u] would fuse two separate components into one. The stack test is what tells a back edge inside the current component apart from a cross edge into a finished one, and undirected DFS needs no such test because it has no cross edges.

Kosaraju: why the second pass paints exactly one component

Collapse each component to a single node and what remains is a DAG. The vertex that finishes last in the first pass always sits in a source of that DAG, a component nothing points into. Reversing every edge turns that source into a sink, so a search started there has nowhere to escape to and stops at the component boundary. Strike out what it painted and the next unvisited latest finisher is a source of whatever is left, so the rule holds all the way down.

Read more

Next up