Graph Theory37 sections · 1633 units
Open in Course

Tarjan Bridge Pseudocode

(DFS with discovery and low)

Here is the bridge detection algorithm:

timer = 0
disc = array of size n, all -1
low = array of size n
bridges = empty list

function dfs(v, parent):
    disc[v] = low[v] = timer
    timer = timer + 1

    for w in adj[v]:
        if w == parent:
            continue
        if disc[w] == -1:
            dfs(w, v)
            low[v] = min(low[v], low[w])
            if low[w] > disc[v]:
                bridges.append((v, w))
        else:
            low[v] = min(low[v], disc[w])

for v from 0 to n - 1:
    if disc[v] == -1:
        dfs(v, -1)

An edge (v,w)(v, w) is a bridge if low[w] > disc[v].