Bridges in graph implementation

Bridges in connected graphs

Given a connected or disconnected graph, find bridges in graph. An edge is called as bridge edge if and only if on removal of that node, graph becomes disconnected if it was connected graph and if it was disconnected then number of components increase by one.  For example in below graphs, bridges are shown in red.

bridges in graph

Concept of detecting bridges in graph will be useful in solving Euler path or tour problem.

Depth First Search of graph can be used to see if graph is connected or not. We can use same concept, one by one remove each edge and see if graph is still connected using DFS. If yes, then edge is not bridge edge, if not, then edge is bridge edge. However, this method entails quite a complexity of O(E * (V+E)) where E is number of edges and V is number of vertices.
Let’s think something better. Consider that we are looking at edge (u,v) in graph. In what condition, we can say that it is bridge edge?
If we can somehow reach node u or any ancestor of u from any node which is decedent of v, that means graph is still connected and (u,v) is not a bridge edge. If above condition is not possible, then (u,v) is bridge.

How can we determine that there is no edge from decedent of v to u or its ancestor? For that we need to maintain time when a node was discovered during depth first search, call is d[].
d[u] is time when node u was discovered using DFS. If d[u] < d[v], means u was discovered before v.
Below is graph with d[] filled for each node.

bridges in graph implementation

Now, figure out the lowest d[x] which can be reached from each node. Reason to find that is to see if there is a node x which is reachable from children of v and has d[x] less than u,i.e. x is ancestor of u reachable from children of v. Store lowest DFS ancestor reachable from node u in an array low[u].

So low[u] = min(low[u], low[v])  for edge (u,v)
Idea here is that if (u,v) is an edge, then either there is no back edge from sub tree of v to u or ancestor of u, in that case low[u] will be lowest. If there is a back edge to x from sub tree of v, then minimum d[x] reached by node in sub tree will be low[u].
Below diagram shows calculation of low[] in graph.

bridges in graph example

Finally, if low[v] > disc [u] that means if discovery time of u is less than least ancestor that can be reached from sub tree of v, we have a bridge, because there is no way we can reach to any ancestor of u once we disconnect edge (u,v).

In above diagram, if we remove edge (3,4), still graph is connected as low[4] = 2 which is less than d[3] which is 3. Hence edge (3,4) is not a bridge.

Lots of theory,lets code it. We will be modifying Depth First Search implementation to keep track of d[] and low[].

Code for finding bridges in graph

#define min(a,b) a>b ? b:a

typedef struct node{
        int value;
        struct node *next;
}Node;
  
Node *graph[NUM_NODE];
  
Node *createNode(int j){
    Node * newNode = (Node *)malloc(sizeof(Node));
    if(newNode){
        newNode->value = j;
        newNode->next = NULL;
    }
    else{
        printf("\n Node cannot be allocated");
    }
    return newNode;
}
  
void addEdge(int i, int j){
    Node * currentNode = graph[i];
    if(!currentNode){
        graph[i] = createNode(j);
    }
    else{
        while(currentNode->next){
            currentNode = currentNode->next;
        }
        currentNode->next = createNode(j);
    }
}

//This function removes a specific edge from undirected graph
void removeEdge(int start, int end){
    printf("Deleting edge (%d, %d)", start, end);
    Node * current  = graph[start];
    Node * previous = current;
    Node * temp = NULL;
    if(current->value == end){
        graph[start] = current->next;
    }
    else{
        while(current && current->value != end){
            previous = current;
            current = current->next;
        }
        previous->next = current->next;
    }
    free(current);

    current = graph[end];
    previous = current;
    if(current->value == start){
        graph[end] = current->next;
    }
    else{
        while(current && current->value != start){
            previous = current;
            current = current->next;
        }
        previous->next = current->next;
    }
    free(current);
}

/*Creating status for finding bridges 
   in graph after removal of edge */
int DFSUtil(int u, int low[],int d[], int parent[], int *time){
    Node * current  = graph[u];
    Node * v = NULL;
    d[u] = low[u] = ++(*time);
    visited[u] = TRUE;

    for(v = current; v != NULL; v = v->next){
        if(visited[v->value] != TRUE){
            parent[v->value] = u;
            DFSUtil(v->value,low,d, parent,time);

            low[u] = min(low[u], low[v->value]);
        }
        if(v->value != parent[u])
            low[u] = min(low[u], low[v->value]);
    }
}

Node * getValidNode(int source, int low[], int d[], int visited[]){
    int i =0;
    Node * currentNode = graph;

    // Find non bridge edge first, 
    //if not available then take any edge.
    while(currentNode){
        if(low[currentNode->value] <= d){ return currentNode; } 
         currentNode = currentNode->next;
    }
    currentNode = graph;
    return currentNode;
}

void dfs(int current, int low[], int d[], int parent[]){
    int time = 0;
  
    /* Getting the next edge to be traversed.
    It should not be a bridge */

    Node *currentNode = getValidNode(current, low, d, visited);
    while(currentNode){
        int a = currentNode->value;

        // Remove the edge which we have traverse from the graph
        removeEdge(current, currentNode->value);
        for(int i=1; i<=NUM_NODE; i++){
            parent[i] = -1;
            low[i] = -1;
            d[i] = -1;
            visited[i] = FALSE;
        }

        /*After removal of node, find if calculation for 
        finding if edge is bridge or not. */
        DFSUtil(a, low, d, parent, &time);

        /* Again go down to the edge which is eligible */
        dfs(a, low, d,parent);

        /* Find next eligible edge */
        temp = getValidNode(current, low, d, visited);
    }
}

// Main function to print Euler path
void printEulerPath(Node * graph[]){
    int startNode = EulerPathExists(graph);
    int parent[NUM_NODE +1];
    int low[NUM_NODE +1];
    int d[NUM_NODE +1];
    int time = 0;

    for(int i=1; i<=NUM_NODE; i++){
        parent[i] = -1;
        low[i] = -1;
        d[i] = -1;
        visited[i] = FALSE;
    }

    // Create book keeping to find if edge is a bridge or not.
    DFSUtil(startNode, low, d, parent, &time);
    dfs(startNode,low, d, parent);
}

int main(){
  addEdge(1,2);
  addEdge(1,3);
  addEdge(2,3);
  addEdge(2,4);
  addEdge(2,4);
  addEdge(3,4);
  addEdge(1,5);
  addEdge(5,6);
  addEdge(6,4);
  addEdge(6,3);
    
  printEulerPath(graph);

  return 0;
}

Complexity of finding bridges in graph code is O(V + E) where V is number of vertices and E is number of edges in graph.

Please share if there is something wrong or missing. If you are interested in contributing to website or have an interview experience to share, please contact us and earn too.