Bi-connected Components

Imagine you have a big network of cities (nodes) connected by roads (edges). Now, if you remove just one city, and the whole network breaks into separate parts, then that city is called an articulation point (or cut vertex).

So, Bi-connected Components(BCC) are the largest possible parts of a graph(subgraph) where no single node removal can disconnect them.

For example, consider the following graph:

The articulation points in the graph are:

{2}
{4}
{6}

The Bi-connected Components (BCCs) in the graph are:

{0, 1, 2, 3}
{2, 4}
{4, 5}
{4, 6}
{6, 7, 8}

Properties of Bi-connected Components

Here are some key properties of bi-connected components:

• Edge: Every edge belongs to exactly one biconnected component.
• Articulation Points: A node can have multiple biconnected components, but it can be an articulation point for only one of them.
• Bridge: An edge that, when removed, increases the number of biconnected components.
• If a graph has no articulation points, the whole graph itself is BCC.

Algorithm for Finding BCC

We use DFS(depth first search) to find biconnected components.

Here's a simple algorithm to find biconnected components in a graph:

1. Perform a Depth First Search (DFS) traversal of the graph.
2. During the DFS traversal, maintain a stack to keep track of the nodes visited.
3. For each node, keep track of the discovery time and low value.
4. When visiting a node, push it onto the stack and update the discovery time and low value.
5. If a back edge is found (i.e., an edge to an already visited node), update the low value of the current node.
6. If the low value of the current node is less than or equal to the discovery time of the parent node, pop nodes from the stack until the current node is reached.
7. The popped nodes form a biconnected component.

Let's say we have this graph

     A
    / \
   B   C
   |   |
   D - E
      / \
     F   G 

The edges are:

AB, AC, BD, CE, EF, EG, DE

If we remove node E, the graph look like this:

     A
    / \
   B   C
   |   
   D        E
           / \
          F   G

A, B, C, and D form one part.

F and G are now completely disconnected from the rest of the graph.

So E is an articulation point.

Biconnected components are −

• {A, B, C, D, E}
• {E, F, G}

Code for Biconnected Components

Let's see the code for finding biconnected components in a above graph:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX 100

int time = 0;
int disc[MAX], low[MAX], parent[MAX];
bool visited[MAX];

typedef struct {
   int u, v;
} Edge;

Edge stack[MAX];
int top = -1;

// Mapping indexes to letters
char nodes[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};

void push(int u, int v) {
   stack[++top].u = u;
   stack[top].v = v;
}

void popUntil(int u, int v) {
   printf("\nBiconnected Component: ");
   while (top >= 0) {
      printf("{%c, %c} ", nodes[stack[top].u], nodes[stack[top].v]);
      if (stack[top].u == u && stack[top].v == v) {
         top--;
         break;
      }
      top--;
   }
}

void DFS(int graph[MAX][MAX], int u, int n) {
   visited[u] = true;
   disc[u] = low[u] = ++time;

   for (int v = 0; v < n; v++) {
      if (graph[u][v]) {
         if (!visited[v]) {
            parent[v] = u;
            push(u, v);

            DFS(graph, v, n);

            low[u] = (low[u] < low[v]) ? low[u] : low[v];

            if (low[v] >= disc[u]) {
               popUntil(u, v);
            }
         } else if (v != parent[u] && disc[v] < disc[u]) {
            low[u] = (low[u] < disc[v]) ? low[u] : disc[v];
            push(u, v);
         }
      }
   }
}

void findBCC(int graph[MAX][MAX], int n) {
   memset(visited, false, sizeof(visited));
   memset(parent, -1, sizeof(parent));
   memset(disc, 0, sizeof(disc));
   memset(low, 0, sizeof(low));

   for (int i = 0; i < n; i++) {
      if (!visited[i]) {
         DFS(graph, i, n);
      }
   }

   if (top >= 0) {
      printf("\nRemaining Biconnected Component: ");
      while (top >= 0) {
         printf("{%c, %c} ", nodes[stack[top].u], nodes[stack[top].v]);
         top--;
      }
   }
}

int main() {
   int n = 7;  
   int graph[MAX][MAX] = {0};

   graph[0][1] = graph[1][0] = 1; // A-B
   graph[0][2] = graph[2][0] = 1; // A-C
   graph[1][3] = graph[3][1] = 1; // B-D
   graph[2][4] = graph[4][2] = 1; // C-E
   graph[4][5] = graph[5][4] = 1; // E-F
   graph[4][6] = graph[6][4] = 1; // E-G
   graph[3][4] = graph[4][3] = 1; // D-E

   printf("Biconnected Components are:\n");
   findBCC(graph, n);

   return 0;
}

Biconnected Components are:

Biconnected Component: {E, F} 
Biconnected Component: {E, G} 
Biconnected Component: {C, A} {E, C} {D, E} {B, D} {A, B} 

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>

using namespace std;

#define MAX 100

int timeCounter = 0;
int disc[MAX], low[MAX], parent[MAX];
bool visited[MAX];

struct Edge {
   int u, v;
};

stack<Edge> edgeStack;

// Mapping indexes to letters
char nodes[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};

void push(int u, int v) {
   edgeStack.push({u, v});
}

void popUntil(int u, int v) {
   cout << "\nBiconnected Component: ";
   while (!edgeStack.empty()) {
      Edge e = edgeStack.top();
      edgeStack.pop();
      cout << "{" << nodes[e.u] << ", " << nodes[e.v] << "} ";
      if (e.u == u && e.v == v) {
         break;
      }
   }
}

void DFS(vector<int> graph[MAX], int u) {
   visited[u] = true;
   disc[u] = low[u] = ++timeCounter;

   for (int v : graph[u]) {
      if (!visited[v]) {
         parent[v] = u;
         push(u, v);

         DFS(graph, v);

         low[u] = min(low[u], low[v]);

         if (low[v] >= disc[u]) {
            popUntil(u, v);
         }
      } else if (v != parent[u] && disc[v] < disc[u]) {
         low[u] = min(low[u], disc[v]);
         push(u, v);
      }
   }
}

void findBCC(vector<int> graph[MAX], int n) {
   memset(visited, false, sizeof(visited));
   memset(parent, -1, sizeof(parent));
   memset(disc, 0, sizeof(disc));
   memset(low, 0, sizeof(low));

   for (int i = 0; i < n; i++) {
      if (!visited[i]) {
         DFS(graph, i);
      }
   }

   if (!edgeStack.empty()) {
      cout << "\nRemaining Biconnected Component: ";
      while (!edgeStack.empty()) {
         Edge e = edgeStack.top();
         edgeStack.pop();
         cout << "{" << nodes[e.u] << ", " << nodes[e.v] << "} ";
      }
   }
}

int main() {
   int n = 7;
   vector<int> graph[MAX];

   graph[0].push_back(1); graph[1].push_back(0); // A-B
   graph[0].push_back(2); graph[2].push_back(0); // A-C
   graph[1].push_back(3); graph[3].push_back(1); // B-D
   graph[2].push_back(4); graph[4].push_back(2); // C-E
   graph[4].push_back(5); graph[5].push_back(4); // E-F
   graph[4].push_back(6); graph[6].push_back(4); // E-G
   graph[3].push_back(4); graph[4].push_back(3); // D-E

   cout << "Biconnected Components are:\n";
   findBCC(graph, n);

   return 0;
}

Biconnected Components are:

Biconnected Component: {E, F} 
Biconnected Component: {E, G} 
Biconnected Component: {C, A} {E, C} {D, E} {B, D} {A, B} 

import java.util.*;

public class BiconnectedComponents {
   
   static final int MAX = 100;
   static int time = 0;
   static int[] disc = new int[MAX], low = new int[MAX], parent = new int[MAX];
   static boolean[] visited = new boolean[MAX];
   static Stack<int[]> edgeStack = new Stack<>();

   // Mapping indexes to letters
   static char[] nodes = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};

   static void push(int u, int v) {
      edgeStack.push(new int[]{u, v});
   }

   static void popUntil(int u, int v) {
      System.out.print("\nBiconnected Component: ");
      while (!edgeStack.isEmpty()) {
         int[] edge = (int[]) edgeStack.pop(); // Explicit cast
         System.out.print("{" + nodes[edge[0]] + ", " + nodes[edge[1]] + "} ");
         if (edge[0] == u && edge[1] == v) {
            break;
         }
      }
   }

   static void DFS(List<Integer>[] graph, int u) {
      visited[u] = true;
      disc[u] = low[u] = ++time;

      for (int v : graph[u]) {
         if (!visited[v]) {
            parent[v] = u;
            push(u, v);

            DFS(graph, v);

            low[u] = Math.min(low[u], low[v]);

            if (low[v] >= disc[u]) {
               popUntil(u, v);
            }
         } else if (v != parent[u] && disc[v] < disc[u]) {
            low[u] = Math.min(low[u], disc[v]);
            push(u, v);
         }
      }
   }

   static void findBCC(List<Integer>[] graph, int n) {
      Arrays.fill(visited, false);
      Arrays.fill(parent, -1);
      Arrays.fill(disc, 0);
      Arrays.fill(low, 0);

      for (int i = 0; i < n; i++) {
         if (!visited[i]) {
            DFS(graph, i);
         }
      }

      if (!edgeStack.isEmpty()) {
         System.out.print("\nRemaining Biconnected Component: ");
         while (!edgeStack.isEmpty()) {
            int[] edge = (int[]) edgeStack.pop(); // Explicit cast
            System.out.print("{" + nodes[edge[0]] + ", " + nodes[edge[1]] + "} ");
         }
      }
   }

   public static void main(String[] args) {
      int n = 7;
      List<Integer>[] graph = new ArrayList[MAX];
      for (int i = 0; i < MAX; i++) {
         graph[i] = new ArrayList<>();
      }

      graph[0].add(1); graph[1].add(0); // A-B
      graph[0].add(2); graph[2].add(0); // A-C
      graph[1].add(3); graph[3].add(1); // B-D
      graph[2].add(4); graph[4].add(2); // C-E
      graph[4].add(5); graph[5].add(4); // E-F
      graph[4].add(6); graph[6].add(4); // E-G
      graph[3].add(4); graph[4].add(3); // D-E

      System.out.println("Biconnected Components are:");
      findBCC(graph, n);
   }
}

Biconnected Components are:

Biconnected Component: {E, F} 
Biconnected Component: {E, G} 
Biconnected Component: {C, A} {E, C} {D, E} {B, D} {A, B} 

class BiconnectedComponents:
   
   def __init__(self, n):
      self.n = n
      self.time = 0
      self.graph = [[] for _ in range(n)]
      self.disc = [-1] * n
      self.low = [-1] * n
      self.parent = [-1] * n
      self.visited = [False] * n
      self.stack = []

      # Mapping indexes to letters
      self.nodes = ['A', 'B', 'C', 'D', 'E', 'F', 'G']

   def add_edge(self, u, v):
      self.graph[u].append(v)
      self.graph[v].append(u)

   def push(self, u, v):
      self.stack.append((u, v))

   def pop_until(self, u, v):
      print("\nBiconnected Component: ", end="")
      while self.stack:
         edge = self.stack.pop()
         print(f"{{{self.nodes[edge[0]]}, {self.nodes[edge[1]]}}} ", end="")
         if edge == (u, v):
            break

   def dfs(self, u):
      self.visited[u] = True
      self.disc[u] = self.low[u] = self.time + 1
      self.time += 1

      for v in self.graph[u]:
         if not self.visited[v]:
            self.parent[v] = u
            self.push(u, v)

            self.dfs(v)

            self.low[u] = min(self.low[u], self.low[v])

            if self.low[v] >= self.disc[u]:
               self.pop_until(u, v)
         elif v != self.parent[u] and self.disc[v] < self.disc[u]:
            self.low[u] = min(self.low[u], self.disc[v])
            self.push(u, v)

   def find_bcc(self):
      for i in range(self.n):
         if not self.visited[i]:
            self.dfs(i)

      if self.stack:
         print("\nRemaining Biconnected Component: ", end="")
         while self.stack:
            edge = self.stack.pop()
            print(f"{{{self.nodes[edge[0]]}, {self.nodes[edge[1]]}}} ", end="")

if __name__ == "__main__":
   n = 7
   bcc = BiconnectedComponents(n)

   bcc.add_edge(0, 1)  # A-B
   bcc.add_edge(0, 2)  # A-C
   bcc.add_edge(1, 3)  # B-D
   bcc.add_edge(2, 4)  # C-E
   bcc.add_edge(4, 5)  # E-F
   bcc.add_edge(4, 6)  # E-G
   bcc.add_edge(3, 4)  # D-E

   print("Biconnected Components are:")
   bcc.find_bcc()

Biconnected Components are:

Biconnected Component: {E, F} 
Biconnected Component: {E, G} 
Biconnected Component: {C, A} {E, C} {D, E} {B, D} {A, B} 

Time Complexity of BCC

• The time complexity of finding biconnected components using the above algorithm is O(V + E), where V is the number of vertices and E is the number of edges in the graph.

Applications of Biconnected Components

Biconnected components are used in various applications, such as:

• Network Reliability: If you want to know the weakest link in a network, BCC helps.
• Bridges & Roads: Cities connected by roads? Find which roads are critical.
• Computer Networks: In network design, BCC helps in fault tolerance.
• File Systems: Used in distributed storage systems to avoid single points of failure.

Conclusion

We have learned about biconnected components in a graph. We have seen how to find biconnected components using a simple algorithm. We have also seen the code in C, C++, Java, and Python. Biconnected components are essential in network design, fault tolerance, and distributed systems.