http://www.geeksforgeeks.org/bridge-in-a-graph/
An edge in an undirected connected graph is a bridge iff removing it disconnects the graph. For a disconnected undirected graph, definition is similar, a bridge is an edge removing which increases number of connected components.
Like Articulation Points,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.
Like Articulation Points,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.
A O(V+E) algorithm to find all Bridges
The idea is similar to O(V+E) algorithm for Articulation Points. 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, 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, “low[v] > disc[u]”.
https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/Bridge.javaThe idea is similar to O(V+E) algorithm for Articulation Points. 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, 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, “low[v] > disc[u]”.
public class Bridge<T> {
private int time;
public Set<Edge<T>> getBridge(Graph<T> graph){
Set<Edge<T>> result = new HashSet<Edge<T>>();
Map<Vertex<T>,Integer> discovery = new HashMap<Vertex<T>,Integer>();
Map<Vertex<T>,Integer> low = new HashMap<Vertex<T>,Integer>();
Map<Vertex<T>,Vertex<T>> parent = new HashMap<Vertex<T>,Vertex<T>>();
Map<Vertex<T>,Boolean> visited = new HashMap<Vertex<T>,Boolean>();
for(Vertex<T> vertex : graph.getAllVertex()){
if(!visited.containsKey(vertex)){
BridgeUtil(vertex,result,discovery,low,parent,visited);
}
}
return result;
}
private void BridgeUtil(Vertex<T> vertex, Set<Edge<T>> result,Map<Vertex<T>,Integer> discovery,
Map<Vertex<T>,Integer> low,Map<Vertex<T>,Vertex<T>> parent,Map<Vertex<T>,Boolean> visited){
visited.put(vertex, true);
discovery.put(vertex, time);
low.put(vertex, time);
time++;
for(Vertex<T> child : vertex.getAdjacentVertexes()){
if(!visited.containsKey(child)){
parent.put(child, vertex);
BridgeUtil(child,result,discovery,low,parent,visited);
if(discovery.get(vertex) < low.get(child) ){
result.add(new Edge<T>(vertex,child));
}
low.put(vertex, Math.min(discovery.get(vertex), low.get(child)));
}else{
if(!child.equals(parent.get(vertex))){
low.put(vertex,Math.min(discovery.get(vertex), low.get(child)));
}
}
}
}
private
int
V;
// No. of vertices
// Array of lists for Adjacency List Representation
private
LinkedList<Integer> adj[];
int
time =
0
;
static
final
int
NIL = -
1
;
// Constructor
Graph(
int
v)
{
V = v;
adj =
new
LinkedList[v];
for
(
int
i=
0
; i<v; ++i)
adj[i] =
new
LinkedList();
}
// Function to add an edge into the graph
void
addEdge(
int
v,
int
w)
{
adj[v].add(w);
// Add w to v's list.
adj[w].add(v);
//Add v to w's list
}
// 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
void
bridgeUtil(
int
u,
boolean
visited[],
int
disc[],
int
low[],
int
parent[])
{
// Count of children in DFS Tree
int
children =
0
;
// Mark the current node as visited
visited[u] =
true
;
// Initialize discovery time and low value
disc[u] = low[u] = ++time;
// Go through all vertices aadjacent to this
Iterator<Integer> i = adj[u].iterator();
while
(i.hasNext())
{
int
v = i.next();
// v is current adjacent of u
// If v is not visited yet, then make it a child
// of u in DFS tree and recur for it.
// If v is not visited yet, then recur for it
if
(!visited[v])
{
parent[v] = u;
bridgeUtil(v, visited, disc, low, parent);
// Check if the subtree rooted with v has a
// connection to one of the ancestors of u
low[u] = Math.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])
System.out.println(u+
" "
+v);
}
// Update low value of u for parent function calls.
else
if
(v != parent[u])
low[u] = Math.min(low[u], disc[v]);
}
}
// DFS based function to find all bridges. It uses recursive
// function bridgeUtil()
void
bridge()
{
// Mark all the vertices as not visited
boolean
visited[] =
new
boolean
[V];
int
disc[] =
new
int
[V];
int
low[] =
new
int
[V];
int
parent[] =
new
int
[V];
// Initialize parent and visited, and ap(articulation point)
// arrays
for
(
int
i =
0
; i < V; i++)
{
parent[i] = NIL;
visited[i] =
false
;
}
// Call the recursive helper function to find Bridges
// in DFS tree rooted with vertex 'i'
for
(
int
i =
0
; i < V; i++)
if
(visited[i] ==
false
)
bridgeUtil(i, visited, disc, low, parent);
}
A simple approach is to one by one remove all edges and see if removal of a edge causes disconnected graph.
1) For every edge (u, v), do following
…..a) Remove (u, v) from graph
..…b) See if the graph remains connected (We can either use BFS or DFS)
…..c) Add (u, v) back to the graph.
…..a) Remove (u, v) from graph
..…b) See if the graph remains connected (We can either use BFS or DFS)
…..c) Add (u, v) back to the graph.
Time complexity of above method is O(E*(V+E)) for a graph represented using adjacency list.