Problem
This problem was asked by Mozilla.
A bridge in a connected (undirected) graph is an edge that, if removed, causes the graph to become disconnected. Find all the bridges in a graph.
Step 1: Understanding the Problem Nuances
Not everyone here has a background in graph theory. Therefore it is important to understand the minute details of the problem before rushing in. The following image shows you a graph and highlights the bridges.
Reading the definition of a bridge, you might notice something. If a node has only one edge, removing that edge disconnects the graph. And this will always hold true. However, this is incomplete. Look at the following graph:
Here the graph has 3 bridges. (1,5) and (3,4) follow our previously established rule. But the rule missed (0,1) which is also a bridge. So how can we proceed?
Step 2: Brute Force Solution
Next, we create our brute force solution. To check if an edge is a bridge, all we have to do is remove the edge and check if the graph is connected (using a DFS/BFS). The procedure for this would look like:
For every edge (u, v), do following:
1) Remove (u, v) from graph
2)See if the graph remains connected (We can either use BFS or DFS)
3) Add (u, v) back to the graph.
The time complexity of the above method is O(E*(V+E)). This is because DFS/BFS all have a V+E time complexity and we repeat them E times.
For good practice, write the code out for this solution before proceeding. In your coding interviews, you only need to acknowledge this solution before proceeding to the more optimal solution.
Step 3: Working out the kinks (optimal soln)
To solve this we need to find some way to track which vertices are "reachable" from other vertices. Reachable is a graph theory concept. Node v is reachable from node u if we can somehow get to v from u using existing edges.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.