Bridges

An interactive, step-by-step visualisation of Bridges.

Category: Graphs
Time complexity: O(V + E)
Space complexity: O(V)

Pseudocode

DFS tracking disc[u] and low[u]
low[v] > disc[u] ⇒ edge (u,v) is a bridge

Reference implementation

def dfs(u, parent):
    disc[u] = low[u] = timer; timer += 1
    for v in adj[u]:
        if v == parent: continue
        if v not in disc:
            dfs(v, u); low[u] = min(low[u], low[v])
            if low[v] &gt; disc[u]: bridges.append((u, v))
        else: low[u] = min(low[u], disc[v])

Open the interactive Bridges visualisation →