Overview
Bridge detection uses DFS discovery times and low-link values to identify edges that have no back edge around them.
CoreSource checked
Bridge Detection
Finds edges whose removal would disconnect an undirected graph.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Intermediate
- Family
- Depth-First Search
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 3
- Formulas
- 1
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
dfs treelow-link valueback edgeconnectivity cut
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)
When to Use
- Use when analyzing graph structure needs dfs tree.
- Use when the input matches the assumptions behind depth-First Search.
When Not to Use
- Avoid when the graph is so large that it needs streaming or external-memory handling.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Finds edges whose removal would disconnect an undirected graph
- Uses dfs tree and low-link value to guide the work.
- Produces visited nodes.
Use Cases
- Analyzing graph structure
- Finding connectivity patterns
- Preparing graph-derived orderings
Inputs
- Graph
- Start nodes or query nodes
- Traversal state
Outputs
- Visited nodes
- Derived graph relationships
Key Formulas (1)
Bridge test
low[v] > discovery[u]
low[v] > discovery[u]Marks edge (u, v) as a bridge when the child subtree cannot reach an ancestor of u.
Pseudocode
- 1.Prepare the inputs and state needed for Bridge Detection.
- 2.Apply the dfs tree step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return visited nodes.
Canonical Example
- Input
- Bridge Detection input with a small representative case
- Output
- Visited nodes
- Explanation
- Bridge Detection applies dfs tree to produce visited nodes.
Implementation Notes
- Keep visitation state and edge classification state separate.
- Keep the dfs tree step separate enough to test independently.
Common Pitfalls
- Mixing directed and undirected edge assumptions can produce incorrect graph relationships.
- Forgetting to check edge cases can make Bridge Detection look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationHighlight active nodes, discovered edges, and the graph structure produced by each step.
Step 1 of 4: Prepare the inputs and state needed for Bridge Detection.
graph-traversal-mechanismNotes
Bridge Detection should be used with the assumptions and tradeoffs of depth-First Search in mind.
Sources (3)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Bridge Detection's standard algorithm design, invariants, and complexity analysis.
Open sourceThe Algorithm Design Manual
BookAlgorithm catalog support for Bridge Detection's problem context, known alternatives, and practical selection tradeoffs.
Open sourceTarjan DFS Linear Graph Algorithms
PaperFoundational reference for low-link DFS methods behind bridge and articulation point detection.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageBridge detection uses DFS discovery and low-link values to find edges whose removal disconnects a graph.
Related Algorithms
Tags
GraphGraph ConnectivityDepth First SearchArticulation Point