Algorithm to find all bridges in a Graph

In this article we'll be discussing on the algorithm to find all bridges in a Graph. Firstly we'll discuss on the Introduction to Bridges. Secondly, we'll understand the bridge concept with a graph example. At the end will write an algorithm & implementation for the same.

Following are the sections of this article:-
Introduction
Example for Bridges
Algorithm
Conclusion

1. Introduction

Consider a Graph(G) which is formed by Vertices(V) and Edges(E), an edge in a Graph(G) between vertices(i.e, u and v, which are the subset of V) is called a Bridge or Cut Egde. After removing it their will be no path between u and v.
In other words, An edge in an Undirected Graph is a Bridge if and only if by removing that edge it disconnects the Graph(G). When an edge is removed the Graph(G) becomes a disconnected graph. And if we continued to remove edges, which increases number of disconnected components. A Graph which doesn't contain any bridge is referred as a Bridgeless Graph.

2. Example for Bridges

Example, Let us consider the below Fig a

Fig a - Undirected Graph

From the above Graph diagram, If an edge 1-0 is removed then there will be no path left to reach from 1 to 0 vertex. Similarly if edge 1-5 is removed, there'll be no path left that connects vertex 1 and 5. These steps are shown in the below diagram Fig b(1 & 2),

(1)
(2)

Fig b(1 & 2) - After removal of Bridges(1-0 and 1-5) from Fig a

Now that the vertex 1 and 5 are disconnected from the main graph. And there are no edges or path through which we can connect them back to the main graph. Hence, in this case the edges from Fig a 1-0 and 1-5 are the Bridges in the Graph.

3. Algorithm

As our main focus to produce this article is to write an algorithm to all the bridges in a Graph, Lets get started.
To find all the bridges in a given Graph(G) formed by Vertices(V) and Edges(E), also u,v are the subset of V that can be an Edge(E) more precisely a Bridge. Following are the ideal or general steps- For every Edge u,v,

a) Remove the Edge u,v from the Graph(G).
b) Check for graph's connectivity i.e, If the Graph(G) still remains connected by traversing to the adjacent node or vertex if any.

Step (b) can be checked by making use of Depth First Search (DFS) algorithm and at the end, Add u,v back to the Graph(G).
So let us discuss a bit about Depth First Search (DFS) algorithm. As its a major idea behind this article to find all bridges in a Graph(G).

• Depth First Search (DFS)
  It is an algorithm for traversing or searching graph or tree data structures that uses backtracking. This algorithm explores all the vertices by going forward if any vertex are present in the graph or uses backtracking to reach its starting or previous vertices. DFS can be implemented by Stack Data structure.
  Typical approach or steps for DFS algorithm are -

1. Start by picking a vertex or node and push all its adjacent vertex into a stack.
2. Now, Pop a node from the stack and push all its adjacent vertex into a stack.
3. Repeat these process until we reach our goal or the stack reaches to its initial state i.e, empty or underflow.

Now we'll focus on, how this Depth First Search algorithm approach can help us to find all bridges in the Graph(G).
In Depth First Search, an edge u,v is a bridge if there does not exist any other path to reach vertex u or an ancestor of u from its subtree rooted with v node or vertex. (where u is parent of v in DFS graph)

Following are the recursive steps, by putting all the previously discussed points in order to find bridge in a Graph(G), These steps are recursively executed until all the Vertices(V) are visited or traversed.

1. Initially all Vertices(V) of Graph(G) are set to 'False'(implies as not visited). Now we start by traversing to a particular vertex u and its value is set to 'True'(implies as visited).
2. Also its respective details like discovery time and low value are updated with the current time(for each iteration this time is incremented by 1).
3. At this stage to check for connectivity, we recursively find the all the vertices v adjacent to u.
4. If vertex v is not visited, we update the parent value for vertex v as vertex u and Goto Step 1.
4a. Also check if the subtree rooted with v has a connection to one of the ancestors of u, find the minimum low value like - low[u] = min(low[u],low[v]).
4b. Check if the lowest vertex reachable from subtree under v is under u in DFS, then the edge u-v is a bridge.
5. If vertex v is visited and it is not the current parent, we need to update the low value of u vertex, low[u] = min(low[u], disc[v]).

• Pseudo Code
  Following is the Pseudo code for the above algorithm,
  function bridgeDetails(start, visited, disc, low, parent). Here this function accepts the parameters-
  The start vertex, the visited array to mark when a node is visited, the disc will hold the discovery time of the vertex, and low will hold information about subtrees. The parent will hold the parent of the current vertex.

Begin

//the value of 'time' will not be initialized for next function calls mark start as visited

   time := 0 
   set disc[start] := time+1 and low[start] := time + 1
   time := time + 1

   for all vertex v in the graph G, do
      if there is an edge between (start, v), then
         if v is visited, then
            parent[v] := start
            bridgeDetails(v, visited, disc, low, parent)
            low[start] := minimum of low[start] and low[v]

            if low[v] > disc[start], then
               display bridges from start to v
         else if v is not the parent of start, then
            low[start] := minimum of low[start] and disc[v]
   done
   
End

• Implementation
  For the above algorithm, We have implemented the code in Python(3.8)

from collections import defaultdict
  
#Using adjacency list representation, This class represents an undirected graph

class Graph:
  
    def __init__(self,vertices):
        self.V= vertices #No. of vertices
        self.graph = defaultdict(list) # default dictionary to store graph
        self.Time = 0
  
    # function to add an edge to graph
    def addingEdge(self,u,v):
        self.graph[u].append(v)
        self.graph[v].append(u)
  
    '''A recursive function that finds and prints bridges
    using DFS traversal
    
    u --> The vertex to be visited next
    visited[] --> A list, which keeps tract of visited vertices
    disc[] --> A list, which Stores discovery times of visited vertices
    parent[] --> A list, which Stores parent vertices in DFS tree'''
    
    def bridgeDetails(self,u, visited, parent, low, disc):
 
        #Count of children in current node 
        children = 0
 
        # Mark the current node as visited and print it
        visited[u]= True
 
        # Initialize discovery time and low value
        disc[u] = self.Time
        low[u] = self.Time
        self.Time += 1
 
        #Recursive execution for all the vertices adjacent to this vertex
        for v in self.graph[u]:
            if visited[v] == False :
                parent[v] = u
                children += 1
                self.bridgeDetails(v, visited, parent, low, disc)

                low[u] = min(low[u], low[v])
  
                ''' If the lowest vertex reachable from subtree
                under v is below u in DFS tree, then u-v is
                a bridge'''
                if low[v] > disc[u]:
                    print ("%d--%d" %(u,v))
                          
            elif v != parent[u]: 
                # Update low value of u for parent function calls.
                low[u] = min(low[u], disc[v])
  
    # DFS based function to find all bridges. It uses recursive
    # function bridgeDetails()
    def findAllBridge(self):
  
     # Mark all the vertices as not visited and Initialize parent and visited
        visited = [False] * (self.V)
        disc = [float("Inf")] * (self.V)
        low = [float("Inf")] * (self.V)
        parent = [-1] * (self.V)
 
        # to find bridges in DFS tree rooted with vertex 'i'
        for i in range(self.V):
            if visited[i] == False:
                self.bridgeDetails(i, visited, parent, low, disc)
  
  
# Program Execution starts from here
if __name__ == '__main__':  

    # Creating a graph given in the above diagram (Fig a)
    g = Graph(6)
    g.addingEdge(0, 1)
    g.addingEdge(0, 3)
    g.addingEdge(0, 2)
    g.addingEdge(1, 5)
    g.addingEdge(2, 3)
    g.addingEdge(2, 4)
    g.addingEdge(3, 4)
    print("\nBridges in the graph are:")
    g.findAllBridge()

# Output @console after running the script
#
# Bridges in the graph are:
# 1--5
# 0--1

The time complexity of the above algorithm is O(V + E) where V is the total number of Vertices and E is the total number of Edges in the Graph(G).

4. Conclusion

Lastly we are at the end of the article. We explored a bit on the Bridge concept of graph. And also we have written an algorithm for the same with the help of DFS algorithm. Their is another concept similar to this called Articulation point or Cut vertex. Which mainly focuses on the vertex participation in a graph.

Hope it was an informative article, Thanks!