Problem 9: Find all the Bridges in a graph [Mozilla]

Graphs, Depth First Search, Graph Theory, Coding Interviews Made Simple

5 min readJan 15, 2024

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.

Join 150K+ tech leaders and get insights on the most important ideas in AI straight to your inbox through my free newsletter- AI Made Simple

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.

If we can manage this, we can identify an edge (u,v) as a bridge, if we come across u before v, and v can’t reach u or any earlier node. In effect, we are identifying nodes that will be isolated if they weren’t connected to a single parent.

More precisely, we can perform a depth-first search, maintaining an array with the time of appearance of each vertex. If a vertex is explored on the first level of the search, appeared[v] = 0. For the second level, appeared[v] = 1, and so on. This tells us which nodes come before other nodes.

At the same time, we store an array that holds the lowest level reachable from any vertex, which will initially be its own depth. For example, suppose we start our search with vertex in the graph above. The value reach[5] initially will be 0. Next, we visit vertex, where we set reach[1] to be 1. We continue our search in this way, increasing the depth at each step. When the stack eventually comes back to 1, reach[1] will be unchanged. In this way, we learn that it is impossible to form a path from 1 back to 0, and so (0, 1) must be a bridge.

def visit(graph, u, v, depth, reach, appeared, bridges):
    appeared[v] = reach[v] = depth

    for neighbor in graph[v]:
        if appeared[neighbor] == -1:
            visit(graph, v, neighbor, depth + 1, reach, appeared, bridges)            if reach[neighbor] == appeared[neighbor]:
                bridges.append((v, neighbor))            reach[v] = min(reach[v], reach[neighbor])        elif neighbor != u:
            reach[v] = min(reach[v], appeared[neighbor])def find_bridges(graph):
    reach = {v : -1 for v in graph}
    appeared = {v : -1 for v in graph}    start = list(graph.keys())[0]
    depth = 0
    bridges = []    visit(graph, start, start, depth, reach, appeared, bridges)    return bridges

The time complexity of this algorithm is the same as that of any depth-first search, O(V + E). We will need to store values in our reach and appeared arrays, and there cannot be as many bridges as vertices, so our space complexity is bounded by O(V).

Save the time, energy, and money you would burn by going through all those videos, courses, products, and ‘coaches’ and easily find all your needs met in one place at ‘Tech Made Simple’! Stay ahead of the curve in AI, software engineering, and the tech industry with expert insights, tips, and resources. 20% off for new subscribers by clicking this link. Subscribe now and simplify your tech journey!