Introduction : Bridge Tree is a term coined by me that refers to the tree formed by shrinking 2-edge biconnected components of the graph . The 2-edge biconnected components shall be referred to as “bridge components” in the further post. The concept is very intuitive so let’s see more about it.
Pre-requisites : Basic Graph Theory. Dfs and Bfs .Bridges in a graph. Biconnected Components and Block-Cut Tree (not really needed to understand but experience with this would be helpful in easier imagination :))
Basic Definitions :
- Bridge edge : A bridge edge in an undirected graph is an edge whose removal increases the number of connected components in the graph by 1. (For more info Bridges in a graph – GeeksforGeeks)
- Articulation Points / Cut Vertices : An articulation point in an undirected graph is a vertex whose removal (and corresponding removal of all the edges incident on that vertex) increases the no of connected components in the graph by at-least 1. (For more info Articulation Points (or Cut Vertices) in a Graph – GeeksforGeeks ).Note : Both the end points of a bridge edge are articulation vertices (given that vertex is not a leaf) . Hence, a graph having articulation vertices might not have bridges but a graph having bridges must have articulation vertices (exception : graph with only 2 nodes and 1 bridge) . eg :
- Biconnected Components : A biconnected component of a given graph is the maximal connected subgraph which does not contain any articulation vertices. (For more info Biconnected components)
eg :
In the following diagram, different colours represent different biconnected components of the graph.
- Block Cut Tree : If each biconnected component of a given graph is shrinked into / represented as a single node called a block, and these blocks are attached to each other at shared vertices (articulation points), then the resulting tree formed is called a Block-Cut tree. (For more info Page on inf.elte.hu ) eg :
The following would be the block-cut tree of the above graph, where A,B,C are blocks attached to the articulation vertices 3 and 4.
A = represents vertices 1,2,3
B = represents vertices 3,4
C = represents vertices 4,5,6
My Definitions :
- Bridge Component : A bridge component of a given graph is the maximal connected subgraph which does not contain any bridge edges. eg :
In the following graph, different coloured vertices lie in different bridge components. The black edges are the normal edges and blue edge represents the bridge edge separating different components
- Bridge Tree : If each bridge component of a given graph is shrinked into/represented as a single node, and these nodes are connected to each other by the bridge edges which separated these components, then the resulting tree formed is called a Bridge Tree. eg :
The following would be the bridge tree formed by shrinking the bridge components of the above given graph.
Detailed Analysis :
What is a Bridge Tree ?
Ans: Bridges in a graph divide the graph into different components such that when we traverse a bridge, we move from one such component to another. Let’s call these components as bridge components. A “bridge tree” is a tree obtained by shrinking each of the bridge components of the graph into a single node such that an edge between two nodes in the resulting tree correspond to the bridge edge in the original graph connecting two different bridge components represented by the two nodes of the tree.
Properties of the Bridge Tree
- Each edge in the bridge tree is the one of the bridge edges in the original graph.
- Since each node in the bridge tree is formed by shrinking the bridge components of original graph, therefore the bridge tree of a graph with N vertices can have at most N nodes (and N-1 edges).
- From the above point, it directly follows that a graph with N vertices can have at most N-1 bridges (why ?? )
How to build the Bridge Tree from a given graph ??
Ans: Now this is the most interesting part of the article and requires good understanding (and imagination) of BFS and DFS. This is an approach which I personally thought of, and you can have your own method of building the tree. (The concept understanding is more important than the code)
Follow the following steps to build the bridge tree :
- Start a dfs from any node of the graph.
- In every step of the dfs, start a bfs to explore the bridge component in which this node lies.
- While exploring this component, as soon as a bridge edge is encountered traverse the bridge edge from the dfs step such that now the dfs step lands to other bridge component.
- Again launch a bfs to explore this component.
- Once this component has been explored, we return to the original component where we had paused the original bfs. Again this bfs continues to explore the remaining bridge component.
- The recursion continues.
In short, each step of the dfs traverses only bridges of the original graph and once a bridge component is reached, the bfs step explores that particular component fully. (See the code for better understanding)
VI tree[N],graph[N];//edge list representation of graph
int U[M],V[M],vis[N],arr[N],T,cmpno;
bool isbridge[M]; // if i'th edge is a bridge edge or not
queue<int> Q[N];
int adj(int u,int e) {
return U[e]==u?V[e]:U[e];
}
int dfs0(int u,int edge) { //mark bridges
vis[u]=1;
arr[u]=T++;
int dbe = arr[u];
for(int i=0; i<SZ(graph[u]); i++) {
int e = graph[u][i];
int w = adj(u,e);
if(!vis[w])dbe = min(dbe,dfs0(w,e));
else if(e!=edge)dbe = min(dbe,arr[w]);
}
if(dbe == arr[u] && edge!=-1)isbridge[edge]=true;
return dbe;
}
void dfs1(int v) { //Build the bridge tree
int currcmp = cmpno;
Q[currcmp].push(v);
vis[v]=1;
while(!Q[currcmp].empty()) {
int u = Q[currcmp].front();
Q[currcmp].pop();
for(int i=0; i<SZ(graph[u]); i++) {
int e = graph[u][i];
int w = adj(u,e);
if(vis[w])continue;
if(isbridge[e]) {
cmpno++;
tree[currcmp].push_back(cmpno);
tree[cmpno].push_back(currcmp);
dfs1(w);
}
else Q[currcmp].push(w),vis[w]=1;
}
}
}
Following is a shorter and more (memory) efficient implementation of bridge tree.
VI tree[N],g[N];//edge list representation of graph
int U[M],V[M],vis[N],arr[N],T,dsu[N];
bool isbridge[M]; // if i'th edge is a bridge edge or not
int adj(int u,int e) {
return U[e]^V[e]^u;
}
int f(int x) {
return dsu[x]=(dsu[x]==x?x:f(dsu[x]));
}
void merge(int a,int b) {
dsu[f(a)]=f(b);
}
int dfs0(int u,int edge) { //mark bridges
vis[u]=1;
arr[u]=T++;
int dbe = arr[u];
for(auto e : g[u]) {
int w = adj(u,e);
if(!vis[w])dbe = min(dbe,dfs0(w,e));
else if(e!=edge)dbe = min(dbe,arr[w]);
}
if(dbe == arr[u] && edge!=-1)isbridge[edge]=true;
else if(edge!=-1)merge(U[edge],V[edge]);
return dbe;
}
void buildBridgeTree(int n,int m) {
for(int i=1; i<=n; i++)dsu[i]=i;
for(int i=1; i<=n; i++)if(!vis[i])dfs0(i,-1);
for(int i=1; i<=m; i++)
if(f(U[i])!=f(V[i])) {
tree[f(U[i])].PB(f(V[i]));
tree[f(V[i])].PB(f(U[i]));
}
}
Applications of the Bridge Tree
- All the problems where Bridge Tree can be used can also be solved by Block-cut tree formed by Biconnected Components but many a times the bridge tree is far more intuitive than the block-cut tree
- eg : Q : Given an undirected connected graph with N nodes and M edges. You can add at-most 1 edge in the graph between any two nodes. Find the minimum number of bridges in the resulting graph.
Ans : Build the bridge tree of the given graph and add 1 edge between the two end points of the diameter such that maximum no of bridges are destroyed. The resulting number of edges in the tree would be the answer. - Also, the above code can be easily modified for maintaining some information of the compressed bridge components if required in the question.
eg : Problem H – Dashboard – 2015 ACM Arabella Collegiate Programming Contest – Codeforces - Other Problems (will be updated as and when found) :
Conclusion : Hope the explanation provided above is clear and understandable. Any comments/suggestions are most welcome.
Happy Coding 🙂
Note : Link to original post
Algorithm Tutorials 
Awesome tutorial, man.
LikeLike
An easy problem : Light OJ 1291 – Real Life Traffic
LikeLike