Finding Bridges in a Graph

From LeetCode:

There are n servers in a network, connected by undirected server-to-server connections. A critical connection is a connection that, if removed, will make some server unable to reach some other server. Find all critical connections.

Input: n = 4, connections = [[0, 1], [1, 2], [2, 0], [1, 3]]
Output: [[1, 3]] # [[3,1]] is also accepted.

This question asks us to find critical server-to-server connections. In more abstract terms, we’re looking to find the bridges of a graph.

Bridges are edges which are essential to a graph’s connectedness. Removing a bridge from a graph will split the graph into two separate subgraphs.

Graph Construction

With graph problems like Alien Dictionary and Connecting Cities at Minimum Cost, you’ll want to define your graph first. Let’s create a dictionary of adjacency lists:

graph = collections.defaultdict(list)

for a, b in connections:
    graph[a].append(b)
    graph[b].append(a)

Bridges and Cycles

A bridge cannot be part of a cycle. If it were, we’d be able access the nodes of the bridge without passing through the bridge itself:

"""
     0
   /   \ 
  1 ––– 2
  | 
  3 ––– 4
"""

# (0, 1), (1, 2) and (0, 2) cannot be bridges.
# For example, we can reach nodes 0 and 1
# without passing through (0, 1) itself.

A graph fully composed of bridges forms a tree:

"""
     0
   /
  1 ––– 2
  |
  3 ––– 4
"""

# Without (0, 2), the cycle between 0, 1, and 2 is broken.
# We're left with a tree of nodes.

Notice that we can identify bridges by removing all of the cycles in a graph.

"""
     0
   
  1     2
  |
  3 ––– 4
"""

# Removing the cycle formed between 0, 1, and 2
# leaves us with the bridges (1, 3), (3, 4).

Cycle Detection

How would we detect a cycle? If you’ve used depth-first search (DFS) frequently enough, you’ll be familiar with:

seen = set()

def DFS(u):
    if u in seen:
        return True # Cycle detected
    seen.add(u)

    for v in graph[u]:
        if DFS(v):
            return True # Propagate detection

This function works well for simple cases, but it’s not enough for the problem we’re tackling. We’re not just concerned with finding cycles –– we want to know which edges in the graph are part of those cycles.

Tracking Node Depths

One of the great things about DFS’ recursive structure is that we can pass on information regarding the nodes we’re visiting.

We established earlier that graphs composed of bridges would form a tree. Starting from any arbitrary root node, let’s go down the supposed tree and:

• Pass on the depth of our current exploration
• Mark nodes we’re visiting with the depth value we’re passing
• See if we encounter a node that already has an assigned depth value. If we do, then we’ve encountered a cycle

depths = [None for _ in range(n)]

edges = set([
    # We do pairwise sorting of (u, v) so that
    # references to (v, u) and (u, v) will
    # correspond to the same edge.
    tuple(sorted([u, v]))
    for u, v in connections
])

def DFS(u, depth):
    if depths[u] is not None:
        return depths[u]
    
    depths[u] = depth

    for v in graph[u]:

        # Ignore edge going back to prev node
        if depths[v] == depth-1:
            continue

        cyclic_depth = DFS(v, depth+1)

        if cyclic_depth <= depth:
            edges.discard(tuple(sorted([u, v])))
            # ...

Looks like we’re getting somewhere. If we find that the cycle_depth value returned from our recursive call is less than or equal to the depth value of our current node, we’ll know that (u, v) cannot be a bridge and can be removed from the set of edges. Essentially, we’re discarding individual edges as we backtrack up the tree.

Covering all the Edges

Note that we don’t immediately return the function at u the moment we detect a cycle at v. Consider the following example:

"""
0 ––– 1 ––– 2
  \   |     |
    \ |     |
5 ––– 4 ––– 3
"""

We start from node 0 and traverse through 1, 2, 3, and 4.

From 4, we move down (4, 1) and detect a cycle consisting of nodes 1 to 4. If we return immediately without exploring the other edges extending from 4, we won’t realise that there’s a larger cycle made up of nodes 0 to 4.

It’s more important for us to propagate the information about the larger cycle, so there’s a real need for us to evaluate all nodes adjacent to 4 before returning.

We’ll tweak our DFS function to return the minimum-value cyclic_depth:

def DFS(u, depth):
    if depths[u] is not None:
        return depths[u]
    
    depths[u] = depth

    min_cyclic_depth = math.inf

    for v in graph[u]:

        if depths[v] == depth-1:
            continue

        cyclic_depth = DFS(v, depth+1)
   
        if cyclic_depth <= depth:
            edges.discard(tuple(sorted([u, v])))
            min_cyclic_depth = min(
                min_cyclic_depth, cyclic_depth
            )

    return min_cyclic_depth

Now all that’s left for us to do is run our DFS on any arbitrary node in the graph. By the end of the algorithm, all of the edges in cycles should be removed, leaving us with just the bridges.

def find_bridges(n, connection):
    
    graph = collections.defaultdict(list)
    depths = [None for _ in range(n)]

    for a, b in connections:
        graph[a].append(b)
        graph[b].append(a)

    edges = set([
        tuple(sorted(c)) for c in connections
    ])

    def DFS(u, depth):
        # Prune edges in cycles

    DFS(0, 0)
    return edges

Given |E| edges, our algorithm runs in O(|E|) space and O(|E|) time.

With that, we’ve solved the Finding Bridges in a Graph problem 🌉🌉🌉.

Full Solution

def find_bridges(n, connection):
    
    graph = collections.defaultdict(list)
    depths = [None for _ in range(n)]

    for a, b in connections:
        graph[a].append(b)
        graph[b].append(a)

    edges = set([
        tuple(sorted(c)) for c in connections
    ])

    def DFS(u, depth):
        
        if depths[u] is not None:
            return depths[u]

        depths[u] = depth

        min_cyclic_depth = math.inf

        for v in graph[u]:
            
            if depths[v] == depth-1:
                continue
                
            cyclic_depth = DFS(v, depth+1)
            if cyclic_depth <= depth:
                edges.discard(tuple(sorted([u, v])))
                min_cyclic_depth = min(
                    min_cyclic_depth, cyclic_depth
                )

        return min_cyclic_depth


    DFS(0, 0)
    return edges