Published by Dimitris Kougioumtzis · Updated
Treat each input edge as undirected. Skip only the parent edge, preserving parallel edges; compare discovery times and low links.
A DFS edge is a bridge when the child subtree has no alternate route to the parent or an earlier ancestor.
When to use Bridges (low-link DFS)
Finding single-edge network vulnerabilities.
Choosing an alternative
Articulation points model vertex removal instead of edge removal.
Worked example: input and state changes
Example input
0,1,1;1,2,1;2,0,1;2,3,1;3,4,1;4,3,1
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initialize graph state.
State at this checkpoint
{ "values": [ "-", "-", "-", "-", "-" ], "active": [], "kind": "graph", "chosen": [], "visited": [] }Step 4: Inspect non-parent edge #2; update low[2]=0.
State at this checkpoint
{ "values": [ "d:0 l:0", "d:1 l:1", "d:2 l:0", "d:-1 l:-1", "d:-1 l:-1" ], "active": [ 2, 0 ], "kind": "graph", "chosen": [], "visited": [], "discovery": [ 0, 1, 2, -1, -1 ], "low": [ 0, 1, 0, -1, -1 ], "bridgeEdges": [], "cutVertices": [] }Step 7: Inspect non-parent edge #5; update low[4]=3.
State at this checkpoint
{ "values": [ "d:0 l:0", "d:1 l:1", "d:2 l:0", "d:3 l:3", "d:4 l:3" ], "active": [ 4, 3 ], "kind": "graph", "chosen": [], "visited": [], "discovery": [ 0, 1, 2, 3, 4 ], "low": [ 0, 1, 0, 3, 3 ], "bridgeEdges": [], "cutVertices": [] }Step 11: Return 2 > 1; low[2]=0, discovery[1]=1.
State at this checkpoint
{ "values": [ "d:0 l:0", "d:1 l:0", "d:2 l:0 cut", "d:3 l:3 cut", "d:4 l:3" ], "active": [ 1, 2 ], "kind": "graph", "chosen": [ 3 ], "visited": [], "discovery": [ 0, 1, 2, 3, 4 ], "low": [ 0, 0, 0, 3, 3 ], "bridgeEdges": [ 3 ], "cutVertices": [ 2, 3 ] }Step 14: Bridge edge indices: 3.
State at this checkpoint
{ "values": [ "d:0 l:0", "d:1 l:0", "d:2 l:0 cut", "d:3 l:3 cut", "d:4 l:3" ], "active": [], "kind": "graph", "chosen": [ 3 ], "visited": [], "result": 1, "bridgeEdges": [ 3 ], "cutVertices": [ 2, 3 ], "discovery": [ 0, 1, 2, 3, 4 ], "low": [ 0, 0, 0, 3, 3 ] }
Expected final state
Bridge edge indices: 3.
Complexity and input bounds
Family: Graphs. Time complexity: O(V + VE) with edge-array scans.
Space complexity: O(V + E) DFS state and edge flags.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Directed edges as source,target,weight; separated by semicolons. Nodes 0–7, positive weights 1–99. Start node is 0. At most 16 edges. Weights are ignored. Edges are undirected; duplicate edges are distinct.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Skip only the parent edge ID, not every edge to the parent vertex: parallel edges can prevent a bridge.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | // Edge arrays from/to/weight; 1..8 vertices indexed 0..vertices-1, 0..16 edges, endpoints in bounds. Weights ignored. Output buffer at least 256 integers. Treat edges as undirected; parallel edges are distinct. Returns count and writes one 0/1 bridge flag per input edge. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(from, to, weight, edges, vertices, output) { let disc = Array(256).fill(0); let low = Array(256).fill(0); let parent = Array(256).fill(0); let parentEdge = Array(256).fill(0); let cursor = Array(256).fill(0); let children = Array(256).fill(0); let dfs = Array(256).fill(0); let cut = Array(256).fill(0); let bridge = Array(256).fill(0); let root = 0; let u = 0; let v = 0; let index = 0; let top = 0; let clock = 0; let count = 0; for (u = 0; u < vertices; u++) { disc[u] = -1; parent[u] = -1; parentEdge[u] = -1; } for (root = 0; root < vertices; root++) { if (disc[root] >= 0) { continue; } disc[root] = clock; low[root] = clock++; dfs[top++] = root; while (top > 0) { u = dfs[top - 1]; index = cursor[u]; while (index < edges && (index == parentEdge[u] || (from[index] != u && to[index] != u))) { index++; } cursor[u] = index + 1; if (index < edges) { v = from[index]; if (v == u) { v = to[index]; } if (disc[v] < 0) { parent[v] = u; parentEdge[v] = index; children[u]++; disc[v] = clock; low[v] = clock++; dfs[top++] = v; } else if (disc[v] < low[u]) { low[u] = disc[v]; } } else { top--; v = parent[u]; if (v < 0) { if (children[u] > 1) { cut[u] = 1; } } else { if (low[u] < low[v]) { low[v] = low[u]; } if (low[u] > disc[v]) { bridge[parentEdge[u]] = 1; } if (parent[v] >= 0 && low[u] >= disc[v]) { cut[v] = 1; } } } } } for (index = 0; index < edges; index++) { output[index] = bridge[index]; count += output[index]; } return count; } |
Source
Primary research source for the algorithm or its underlying method. The playground is a bounded teaching implementation, not the publication's original program.
- A note on finding the bridges of a graph
R.Endre Tarjan (1974). Research paper.