2–Edge Connectivity in a graph
Given an undirected connected graph, check if the graph is 2–edge connected and return the bridges (if any).
A connected graph is 2–edge connected if it remains connected whenever any edges are removed. A bridge (or cut arc) is an edge of a graph whose deletion increases its number of connected components, i.e., an edge whose removal disconnects the graph. So if any such bridge exists, the graph is not 2–edge connected.
For example, the following graph has 6 vertices and 3 bridges (highlighted in red):
Prerequisite:
A simple approach would be to remove each edge from the graph one by one and run Depth–first search (DFS) or Breadth–first search (BFS) starting from any vertex. If the DFS or BFS covers all nodes in the graph, then the removed edge cannot be a bridge. If not, that edge is a bridge. The time complexity of this solution is O(E × (V + E)), where V and E are the total number of vertices and edges in the graph, respectively.
We can solve this problem efficiently in one pass of DFS. When we do a DFS from vertex v in an undirected graph, there could be edges going out of the subtree, i.e., back edges. We can say that the graph is 2–edge connected if and only if for every edge u —> v in the graph, there is at least one back-edge that is going out of a subtree rooted at v to some ancestor of u. When we say subtree rooted at v, we mean all of v's descendants, including the vertex itself.
In other words, when we backtrack from a vertex v, we need to ensure that there is some back-edge from some descendant of v (including v) to some proper ancestor (parent or above) of v.
How can we modify DFS so that we can check if there is a back-edge going out of every subtree?
We can modify DFS such that DFS(v) returns the smallest arrival time to which there is a back edge from the subtree rooted at v. For example, let arrival(v) be the arrival time of vertex v in the DFS. If there is a back edge out of the subtree rooted at v, it is to something visited before v, and therefore with a smaller arrival value. Remember for a back edge u —> v in a graph, arrival[u] > arrival[v].
Suppose four edges are going out of a subtree rooted at v to vertex a, b, c and d, with arrival time A(a), A(b), A(c) and A(d), respectively. We look at their four arrival times and consider the smallest among them, that will be the value returned by DFS(v), i.e., DFS(v) returns the minimum min of A(a), A(b), A(c), and A(d). But before returning, we have to check that min is less than the A(v). If min is less than the A(v), then that means that at least one back-edge is going out of the subtree rooted at v. If not, we can say that (parent[v], v) is a bridge.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
#include <iostream> #include <vector> #include <set> using namespace std; typedef pair<int, int> Edge; class Graph { public: // a vector of vectors to represent an adjacency list vector<vector<int>> adjList; // Graph Constructor Graph(vector<Edge> const &edges, int n) { // resize the vector to hold `n` elements of type `vector<int>` adjList.resize(n); // add edges to the undirected graph for (auto &edge: edges) { adjList[edge.first].push_back(edge.second); adjList[edge.second].push_back(edge.first); } } }; // Perform DFS on the graph starting from vertex `v` and find // all bridges in the process int DFS(Graph const &graph, int v, vector<bool> visited, vector<int> &arrival, int parent, int &time, auto &bridges) { // set the arrival time of vertex `v` arrival[v] = ++time; // mark vertex as visited visited[v] = true; // initialize `t` with the arrival time of vertex `v` int t = arrival[v]; // (v, w) forms an edge for (int w: graph.adjList[v]) { // if `w` is not visited if (!visited[w]) { t = min(t, DFS(graph, w, visited, arrival, v, time, bridges)); } // if `w` is visited, and `w` is not a parent of `v` else if (w != parent) { // If vertex `w` is already visited, there is a back edge starting // from `v`. Note that as visited[u] is already // true, arrival[u] is already defined t = min(t, arrival[w]); } } // if the value of `t` remains unchanged, i.e., it is equal // to the arrival time of vertex `v`, and if `v` is not the root node, // then (parent[v] —> v) forms a bridge if (t == arrival[v] && parent != -1) { bridges.insert({parent, v}); } // return the minimum arrival time return t; } set<Edge> findBridges(Graph const &graph, int n) { // to keep track of whether a vertex is visited or not vector<bool> visited(n); // stores arrival time of a node in DFS vector<int> arrival(n); int start = 0, parent = -1, time = 0; set<Edge> bridges; // As the given graph is connected, DFS will cover every node DFS(graph, start, visited, arrival, parent, time, bridges); return bridges; } void printEdges(auto const &edges) { for (auto const &edge: edges) { cout << '(' << edge.first << ", " << edge.second << ") "; } } // 2–edge connectivity in a graph int main() { // vector of graph edges vector<Edge> edges = { {0, 2}, {1, 2}, {2, 3}, {2, 4}, {3, 4}, {3, 5} }; // total number of nodes in the graph (0 to 6) int n = 10; // build a graph from the given edges Graph graph(edges, n); // find and print bridges auto bridges = findBridges(graph, n); if (bridges.size() != 0) { cout << "Bridges are "; printEdges(bridges); } else { cout << "Graph is 2– Connected"; } return 0; } |
Output:
Bridges are (0, 2) (2, 1) (3, 5)
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 |
import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.HashSet; import java.util.Set; // A class to store a graph edge class Edge { int source, dest; public Edge(int source, int dest) { this.source = source; this.dest = dest; } @Override public String toString() { return "(" + source + ", " + dest + ')'; } } // A class to represent a graph object class Graph { // A list of lists to represent an adjacency list List<List<Integer>> adjList = null; // Constructor Graph(List<Edge> edges, int n) { adjList = new ArrayList<>(); for (int i = 0; i < n; i++) { adjList.add(new ArrayList<>()); } // add edges to the undirected graph for (Edge edge: edges) { int src = edge.source; int dest = edge.dest; adjList.get(src).add(dest); adjList.get(dest).add(src); } } } class Main { // Perform DFS on the graph starting from vertex `v` and find // all bridges in the process public static int DFS(Graph graph, int v, boolean[] visited, int[] arrival, int parent, int time, Set<Edge> bridges) { // set the arrival time of vertex `v` arrival[v] = ++time; // mark vertex as visited visited[v] = true; // initialize `t` with the arrival time of vertex `v` int t = arrival[v]; // (v, w) forms an edge for (int w: graph.adjList.get(v)) { // if `w` is not visited if (!visited[w]) { t = Integer.min(t, DFS(graph, w, visited, arrival, v, time, bridges)); } // if `w` is visited, and `w` is not a parent of `v` else if (w != parent) { // If vertex `w` is already visited, there is a back edge starting // from `v`. Note that as visited[u] is already // true, arrival[u] is already defined t = Integer.min(t, arrival[w]); } } // if the value of `t` remains unchanged, i.e., it is equal // to the arrival time of vertex `v`, and if `v` is not the root node, // then (parent[v] —> v) forms a bridge if (t == arrival[v] && parent != -1) { bridges.add(new Edge(parent, v)); } // return the minimum arrival time return t; } public static Set<Edge> findBridges(Graph graph, int n) { // to keep track of whether a vertex is visited or not boolean[] visited = new boolean[n]; // stores arrival time of a node in DFS int[] arrival = new int[n]; int start = 0, parent = -1, time = 0; Set<Edge> bridges = new HashSet<>(); // As the given graph is connected, DFS will cover every node DFS(graph, start, visited, arrival, parent, time, bridges); return bridges; } public static void main(String[] args) { // (u, v) triplet represent undirected edge from vertex `u` to vertex `v` List<Edge> edges = Arrays.asList( new Edge(0, 2), new Edge(1, 2), new Edge(2, 3), new Edge(2, 4), new Edge(3, 4), new Edge(3, 5) ); // total number of nodes in the graph (0 to 6) int n = 6; // construct graph Graph graph = new Graph(edges, n); // find and print bridges Set<Edge> bridges = findBridges(graph, n); if (bridges.size() != 0) { System.out.println("Bridges are " + bridges); } else { System.out.println("Graph is 2–Edge Connected"); } } } |
Output:
Bridges are [(0, 2), (2, 1), (3, 5)]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
# A class to represent a graph object class Graph: # Constructor def __init__(self, edges, n): # A list of lists to represent an adjacency list self.adjList = [[] for _ in range(n)] # add edges to the undirected graph for (src, dest) in edges: self.adjList[src].append(dest) self.adjList[dest].append(src) # Perform DFS on the graph starting from vertex `v` and find # all bridges in the process def DFS(graph, v, visited, arrival, parent, time, bridges): # set the arrival time of vertex `v` time = time + 1 arrival[v] = time # mark vertex as visited visited[v] = True # initialize `t` with the arrival time of vertex `v` t = arrival[v] # (v, w) forms an edge for w in graph.adjList[v]: # if `w` is not visited if not visited[w]: t = min(t, DFS(graph, w, visited, arrival, v, time, bridges)) # if `w` is visited, and `w` is not a parent of `v` elif w != parent: # If vertex `w` is already visited, there # is a back edge starting from `v`. Note that as `visited[u]` # is already true, arrival[u] is already defined t = min(t, arrival[w]) # if the value of `t` remains unchanged, i.e., it is equal # to the arrival time of vertex `v`, and if `v` is not the root node, # then (parent[v] —> v) forms a bridge if t == arrival[v] and parent != -1: bridges.add((parent, v)) # return the minimum arrival time return t def findBridges(graph, n): # to keep track of whether a vertex is visited or not visited = [False] * n # stores arrival time of a node in DFS arrival = [None] * n start = 0 parent = -1 time = 0 bridges = set() # As the given graph is connected, DFS will cover every node DFS(graph, start, visited, arrival, parent, time, bridges) return bridges if __name__ == '__main__': # (u, v) triplet represent undirected edge from vertex `u` to vertex `v` edges = [(0, 2), (1, 2), (2, 3), (2, 4), (3, 4), (3, 5)] # total number of nodes in the graph (0 to 6) n = 6 # construct graph graph = Graph(edges, n) bridges = findBridges(graph, n) if bridges: print('Bridges are', bridges) else: print('Graph is 2–Edge Connected') |
Output:
Bridges are {(0, 2), (2, 1), (3, 5)}
The time complexity of the above solution is O(V + E), where V and E are the total number of vertices and edges in the graph, respectively.
Reference: Dr. Naveen Garg, IIT–D (Lecture – 28 Applications of DFS)
Image credits: http://mathworld.wolfram.com/GraphBridge.html
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)