{"id":27123,"date":"2018-01-03T21:33:22","date_gmt":"2018-01-03T16:03:22","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27123"},"modified":"2018-01-03T21:33:22","modified_gmt":"2018-01-03T16:03:22","slug":"python-programming-bridges-graph","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-programming-bridges-graph\/","title":{"rendered":"PYTHON programming Bridges in a graph"},"content":{"rendered":"

An edge in an undirected connected graph is a bridge iff removing it disconnects the graph. <\/span>For a disconnected undirected graph, definition is similar, a bridge is an edge removing which increases number of connected components.
\nLike Articulation Points<\/a>,bridges represent vulnerabilities in a connected network and are useful for designing reliable networks. For example, in a wired computer network, an articulation point indicates the critical computers and a bridge indicates the critical wires or connections.<\/p>\n

Following are some example graphs with bridges highlighted with red color.<\/p>\n

How to find all bridges in a given graph?<\/strong>
\nA simple approach is to one by one remove all edges and see if removal of a edge causes disconnected graph. Following are steps of simple approach for connected graph.<\/p>\n

1) For every edge (u, v), do following
\n\u2026..a) Remove (u, v) from graph
\n..\u2026b) See if the graph remains connected (We can either use BFS or DFS)
\n\u2026..c) Add (u, v) back to the graph.<\/p>\n

Time complexity of above method is O(E*(V+E)) for a graph represented using adjacency list. Can we do better?<\/p>\n[ad type=”banner”]\n

A O(V+E) algorithm to find all Bridges<\/strong>
\nThe idea is similar to O(V+E) algorithm for Articulation Points<\/a>. We do DFS traversal of the given graph. In DFS tree an edge (u, v) (u is parent of v in DFS tree) is bridge if there does not exit any other alternative to reach u or an ancestor of u from subtree rooted with v. As discussed in the previous post<\/a>, the value low[v] indicates earliest visited vertex reachable from subtree rooted with v. The condition for an edge (u, v) to be a bridge is, \u201clow[v] > disc[u]\u201d<\/em>.<\/p>\n

<\/div> 
# Python program to find bridges in a given undirected graph#Complexity : O(V+E)  from collections import defaultdict  #This class represents an undirected graph using adjacency list representationclass 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 addEdge(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[] --> keeps tract of visited vertices    disc[] --> Stores discovery times of visited vertices    parent[] --> Stores parent vertices in DFS tree'''    def bridgeUtil(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         #Recur for all the vertices adjacent to this vertex        for v in self.graph[u]:            # If v is not visited yet, then make it a child of u            # in DFS tree and recur for it            if visited[v] == False :                parent[v] = u                children += 1                self.bridgeUtil(v, visited, parent, low, disc)                 # Check if the subtree rooted with v has a connection to                # one of the ancestors of u                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 bridgeUtil()    def bridge(self):          # Mark all the vertices as not visited and Initialize parent and visited,         # and ap(articulation point) arrays        visited = [False] * (self.V)        disc = [float("Inf")] * (self.V)        low = [float("Inf")] * (self.V)        parent = [-1] * (self.V)         # Call the recursive helper function to find bridges        # in DFS tree rooted with vertex 'i'        for i in range(self.V):            if visited[i] == False:                self.bridgeUtil(i, visited, parent, low, disc)           # Create a graph given in the above diagramg1 = Graph(5)g1.addEdge(1, 0)g1.addEdge(0, 2)g1.addEdge(2, 1)g1.addEdge(0, 3)g1.addEdge(3, 4)   print "Bridges in first graph "g1.bridge() g2 = Graph(4)g2.addEdge(0, 1)g2.addEdge(1, 2)g2.addEdge(2, 3)print "\\nBridges in second graph "g2.bridge()   g3 = Graph (7)g3.addEdge(0, 1)g3.addEdge(1, 2)g3.addEdge(2, 0)g3.addEdge(1, 3)g3.addEdge(1, 4)g3.addEdge(1, 6)g3.addEdge(3, 5)g3.addEdge(4, 5)print "\\nBridges in third graph "g3.bridge()  <\/code><\/pre> <\/div>\n
Output:<\/p>\n
Bridges in first graph\r\n3 4\r\n0 3\r\n\r\nBridges in second graph\r\n2 3\r\n1 2\r\n0 1\r\n\r\nBridges in third graph\r\n1 6<\/pre>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
PYTHON programming – Bridges in a graph – An edge in an undirected connected graph is a bridge iff removing it disconnects the graph.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,78385,73906,4148],"tags":[79021,80897,80898,80899,80896,80900,80902,80901],"class_list":["post-27123","post","type-post","status-publish","format-standard","hentry","category-coding","category-connectivity","category-graph-algorithms","category-python","tag-articulation-points-and-bridges","tag-articulation-points-in-a-graph","tag-bridge-edge-seo","tag-bridge-graph-excel","tag-cut-vertex-graph-theory","tag-give-a-linear-time-algorithm-for-finding-the-bridges-in-a-graph","tag-graph-theory-bridge","tag-inverted-graph"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27123","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27123"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27123\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27123"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27123"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27123"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}