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:
/ \ / \
/ \ / \
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
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
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
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)
Thank you for sparing your valuable time to read this article. You can check out other articles as well:
- Implementing Quick Select in Python
- Determine Whether A Given Undirected Graph is Two-Colorable in Python