Question

In: Computer Science

Given a connected graph G with n vertices. We say an edge of G is a...

Given a connected graph G with n vertices. We say an edge of G is a bridge if the graph becomes a disconnected graph after removing the edge. Give an O(m + n) time algorithm that finds all the bridges. (Partial credits will be given for a polynomial time algorithm.) (Hint: Use DFS)

Solutions

Expert Solution

A bridge is defined as an edge which, when removed, makes the graph disconnected (or more precisely, increases the number of connected components in the graph).

Informally, the problem is formulated as follows: given a map of cities connected with roads, find all "important" roads, i.e. roads which, when removed, cause disappearance of a path between some pair of cities.

The algorithm described here is based on depth first search and has O(N+M)O(N+M) complexity, where N is the number of vertices and MM is the number of edges in the graph.

Note that there also is also the article Finding Bridges Online - unlike the offline algorithm described here, the online algorithm is able to maintain the list of all bridges in a changing graph (assuming that the only type of change is addition of new edges).

Algorithm;

Pick an arbitrary vertex of the graph root and run depth first search from it. Note the following fact (which is easy to prove):

  • Let's say we are in the DFS, looking through the edges starting from vertex v. The current edge (v,to)(v,to) is a bridge if and only if none of the vertices to and its descendants in the DFS traversal tree has a back-edge to vertex v or any of its ancestors. Indeed, this condition means that there is no other way from v to to except for edge (v,to)(v,to).

Now we have to learn to check this fact for each vertex efficiently. We'll use "time of entry into node" computed by the depth first search.

So, let tin[v]tin[v] denote entry time for node v. We introduce an array low which will let us check the fact for each vertex v. low[v]low[v] is the minimum of tin[v]tin[v], the entry times tin[p]tin[p] for each node pp that is connected to node vv via a back-edge (v,p)(v,p) and the values of low[to]low[to] for each vertex to which is a direct descendant of v in the DFS tree:

low[v]=min⎧⎩⎨tin[v]tin[p]low[to] for all p for which (v,p) is a back edge for all to for which (v,to) is a tree edgelow[v]=min{tin[v]tin[p] for all p for which (v,p) is a back edgelow[to] for all to for which (v,to) is a tree edge

Now, there is a back edge from vertex v or one of its descendants to one of its ancestors if and only if vertex v has a child to for which low[to]≤tin[v]low[to]≤tin[v]. If low[to]=tin[v]low[to]=tin[v], the back edge comes directly to v, otherwise it comes to one of the ancestors of v.

Thus, the current edge (v,to)(v,to) in the DFS tree is a bridge if and only if low[to]>tin[v]low[to]>tin[v].

Implementation

The implementation needs to distinguish three cases: when we go down the edge in DFS tree, when we find a back edge to an ancestor of the vertex and when we return to a parent of the vertex. These are the cases:

  • visited[to]=falsevisited[to]=false - the edge is part of DFS tree;
  • visited[to]=truevisited[to]=true && to≠parentto≠parent - the edge is back edge to one of the ancestors;
  • to=parentto=parent - the edge leads back to parent in DFS tree.

To implement this, we need a depth first search function which accepts the parent vertex of the current node.

Main function is find_bridges; it performs necessary initialization and starts depth first search in each connected component of the graph.

Function IS_BRIDGE(a, b) is some function that will process the fact that edge (a,b)(a,b) is a bridge, for example, print it.

Note that this implementation malfunctions if the graph has multiple edges, since it ignores them. Of course, multiple edges will never be a part of the answer, so IS_BRIDGE can check additionally that the reported bridge is not a multiple edge. Alternatively it's possible to pass to dfs the index of the edge used to enter the vertex instead of the parent vertex (and store the indices of all vertices).


Related Solutions

Given a connected graph G where edge costs are pair-wise distinct, prove or disprove that the...
Given a connected graph G where edge costs are pair-wise distinct, prove or disprove that the G has a unique MST. Please write Pseudo-code for the algorithms.
Given an undirected graph G = (V,E), consisting of n vertices and m edges, with each...
Given an undirected graph G = (V,E), consisting of n vertices and m edges, with each edge labeled from the set {0,1}. Describe and analyze the worst-case time complexity of an efficient algorithm to find any cycle consisting of edges whose labels alternate 0,1.
Prove a connected simple graph G with 16 vertices and 117 edges is not Eulerian.
Prove a connected simple graph G with 16 vertices and 117 edges is not Eulerian.
An eulerian walk is a sequence of vertices in a graph such that every edge is...
An eulerian walk is a sequence of vertices in a graph such that every edge is traversed exactly once. It differs from an eulerian circuit in that the starting and ending vertex don’t have to be the same. Prove that if a graph is connected and has at most two vertices of odd degree, then it has an eulerian walk.
Suppose G is a connected cubic graph (regular of degree 3) and e is an edge...
Suppose G is a connected cubic graph (regular of degree 3) and e is an edge such that G − e has two connected components G1 and G2 (a) Explain what connected means. (b) We say that e is a____________ of G (c) show that G1 has an odd number of vertices. (d) draw a connected cubic graph G with an edge e as above.
You are given a directed graph G(V,E) with n vertices and m edges. Let S be...
You are given a directed graph G(V,E) with n vertices and m edges. Let S be the subset of vertices in G that are able to reach some cycle in G. Design an O(n + m) time algorithm to compute the set S. You can assume that G is given to you in the adjacency-list representation.
Let G be a simple undirected graph with n vertices where n is an even number....
Let G be a simple undirected graph with n vertices where n is an even number. Prove that G contains a triangle if it has at least (n^2 / 4) + 1 edges using mathematical induction.
Show that any graph with n vertices and δ(G) ≥ n/2 + 1 has a triangle.
Show that any graph with n vertices and δ(G) ≥ n/2 + 1 has a triangle.
An m × n grid graph has m rows of n vertices with vertices closest to...
An m × n grid graph has m rows of n vertices with vertices closest to each other connected by an edge. Find the greatest length of any path in such a graph, and provide a brief explanation as to why it is maximum. You can assume m, n ≥ 2. Please provide an explanation without using Hamilton Graph Theory.
You are given an undirected graph G = ( V, E ) in which the edge...
You are given an undirected graph G = ( V, E ) in which the edge weights are highly restricted. In particular, each edge has a positive integer weight from 1 to W, where W is a constant (independent of the number of edges or vertices). Show that it is possible to compute the single-source shortest paths in such a graph in O(E+V) time.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT