#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/bridges-and-articulation-points/tarjan-bridge-pseudocode

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/bridges-and-articulation-points/tarjan-bridge-pseudocode

Repovive

Tarjan Bridge Pseudocode - Bridges and Articulation Points | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

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)$ is a bridge if low[w] > disc[v].