Find all Bridges of a Graph in Python

This tutorial will show you how to find all bridges of a graph in Python. Before we go forward, let me tell you about bridges of the graph in brief.

Bridges of a graph are the edges that if removed from the graph would increase the number of connected components in the graph. Let’s consider a scenario where:

2 is the boyfriend of 3.

2’s friends are 0 and 1, and 3’s friends are 4 and 5.

0,1 and 4,5 only meet each other when 2 and 3 have a combined party.

But if 2 breakups with 3 then: 0,1 and 4,5 won’t meet each other at all.

So the relation between 2 and 3 acts as a bridge between these two groups.

Following is the graphical representation of the above scenario:

0 5

/ \ / \

1 ——– 2 — 3 ————- 4

Here the edge 2 — 3 is a bridge because removing that edge disconnects the graph into two separate components. However, none of the other edges are a bridge because removing them does not disconnect the graph into separate components.

In this tutorial, you are going to learn how to find all the bridges for a given undirected graph.

Important Property of Bridges of a Graph

An edge is a bridge of a graph if and only if it does not lie on any simple cycle in the graph. This means that any edge that lies in a cycle is not a bridge and any edge that does not lie on a cycle is a bridge.

How to find all bridges of a graph?

For this purpose, let’s first define a quantity which we will call : low_link[v] for each vertex v such that low_link[v ] = min( dfs_ord[v], dfs_ord[u] : for any vertex u reachable from v via unused edges after visiting v)

We can compute low_link by noticing that the low link of a particular vertex v is the minimum low link of all vertices adjacent to v via unused edges. This is because if we can reach vertex u via some path of length longer than one, then one of the vertices that we are adjacent to is on that path and can therefore also reach it. In other words, we can write low_link[v ] = min (dfs_ord[v ], min low_link[u] for all u∈V and u adjacent to v and edge(u,v) is unused).

This means that at each vertex v during the depth-first search, we should traverse all of our children and then update our low_link to the minimum out of all of the adjacent vertices that are connected to us by an unused edge.

Observe that low_link[v] describes the earliest vertex that we can travel back to after reaching v for the first time without using any already-used edges. If it is possible to travel to v ’s parent u, then we could travel from v to u and then back down to v, and hence there is a cycle containing the edge (u, v ). If we can travel to any vertex that we visited before u, then we can travel from there to u by following the edges that the depth-first search took, and hence there is a cycle containing (u, v ). Otherwise, if it is not possible to reach any vertex that we visited before v, then there is no way to cycle back to v and hence there is no cycle containing (u, v ). Let (u, v ) be an edge oriented in the direction that the depth-first search traverses it.

Using the observation above, (u, v) is a bridge if and only if: low_link[v] > dfs_num[u]

Pseudocode for the solution

1: function FIND_BRIDGES(G = (V, E))

2: Set dfs_counter = 1

3: Set dfs_ord[u] = low_link[u] = null for all u ∈ V

4: for each vertex u = 1 to n do

5: if dfs_ord[u] = null then

6: DFS(u)

7: end function

9: function DFS(u)

10: dfs_ord[u] = low_link[u] = dfs_counter

11: dfs_counter = dfs_counter + 1

12: for all edges e = (u, v ) adjacent to u do

13: if edge e has not been traversed yet then

14: if dfs_ord[v ] = null then

15: Mark e as traversed

16: DFS(v)

17: if low_link[v ] > dfs_ord[u] then

18: The edge e is a bridge

19: low_link[u] = min(low_link[u], low_link[v ])

20: end function

Complexity Analysis

Since we can compute dfs_ord and low_link in O(V + E) time and use them to determine the bridges, we can determine the bridges in O(V + E) time as well.

Implementation in Python to find all bridges of a graph

Below is our Python code:

import math


def find_bridges(adj_list):
    """
    Input: an undirected graph in the form of an adjacency list
    Output: prints all the bridges found in the graph 
    Complexity: O(V+E) where V=number of vetices in the graph 
    and E = number of edges in the graph
    """
    dfs_counter = 0
    n = len(adj_list) 
    dfs_ord = [math.inf] * n
    low_link = [math.inf] * n
    visited_vertices = [False] * n
    parent_vertex = [-1] * n
    for i in range(n):
        if visited_vertices[i] == False:
            dfs(i, visited_vertices, parent_vertex, low_link, dfs_ord, dfs_counter, adj_list)

def dfs(u, visited_vertices, parent_vertex, low_link, dfs_ord, dfs_counter, adj_list):
    """
    dfs function for finding the bridges in the graph
    """
    visited_vertices[u] = True
    dfs_ord[u] = dfs_counter
    low_link[u] = dfs_counter
    dfs_counter += 1
    for v in adj_list[u]:
        if visited_vertices[v] == False:
            parent_vertex[v] = u
            dfs(v, visited_vertices, parent_vertex, low_link, dfs_ord, dfs_counter, adj_list)

            low_link[u] = min(low_link[u], low_link[v])
            if low_link[v] > dfs_ord[u]:
                print(" " + str(u) + " " + str(v) + " ")

        elif v!= parent_vertex[u]:
            low_link[u] = min(low_link[u], dfs_ord[v])

Let’s run the example given in the first section of the blog:

graph = [ [ 1, 2],
          [ 0, 2],
          [ 0, 1, 3],
          [ 2, 4, 5],
          [ 3, 5],
          [ 3, 4] ]
find_bridges(graph)

Output:

2 3

Thank you for sparing your valuable time to read this article. You can check out other articles as well: