C++ Programming Code Examples C++ > Computer Graphics Code Examples C++ Program to Find the Edge Connectivity of a Graph C++ Program to Find the Edge Connectivity of a Graph This is a C++ Program to find edge connectivity of a graph. An edge in an undirected connected graph is a bridge if 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. // A C++ program to find bridges in a given undirected graph #include<iostream> #include <list> #define NIL -1 using namespace std; // A class that represents an undirected graph class Graph { int V; // No. of vertices list<int> *adj; // A dynamic array of adjacency lists void bridgeUtil(int v, bool visited[], int disc[], int low[], int parent[]); public: Graph(int V); // Constructor void addEdge(int v, int w); // function to add an edge to graph void bridge(); // prints all bridges }; Graph::Graph(int V) { this->V = V; adj = new list<int> [V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); adj[w].push_back(v); // Note: the graph is undirected } void Graph::bridgeUtil(int u, bool visited[], int disc[], int low[], int parent[]) { // A static variable is used for simplicity, we can avoid use of static variable by passing a pointer. static int time = 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 list<int>::iterator i; for (i = adj[u].begin(); i != adj[u].end(); ++i) { int v = *i; // v is current adjacent of u // 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] = 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]) cout << u << " " << v << endl; } // Update low value of u for parent function calls. else if (v != parent[u]) low[u] = min(low[u], disc[v]); } } // DFS based function to find all bridges. It uses recursive function bridgeUtil() void Graph::bridge() { // Mark all the vertices as not visited bool *visited = new bool[V]; int *disc = new int[V]; int *low = new int[V]; int *parent = new int[V]; // Initialize parent and visited 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); } // Driver program to test above function int main() { // Create graphs given in above diagrams cout << "\nBridges in first graph \n"; Graph g1(5); g1.addEdge(1, 0); g1.addEdge(0, 2); g1.addEdge(2, 1); g1.addEdge(0, 3); g1.addEdge(3, 4); g1.bridge(); cout << "\nBridges in second graph \n"; Graph g2(4); g2.addEdge(0, 1); g2.addEdge(1, 2); g2.addEdge(2, 3); g2.bridge(); cout << "\nBridges in third graph \n"; Graph g3(7); g3.addEdge(0, 1); g3.addEdge(1, 2); g3.addEdge(2, 0); g3.addEdge(1, 3); g3.addEdge(1, 4); g3.addEdge(1, 6); g3.addEdge(3, 5); g3.addEdge(4, 5); g3.bridge(); return 0; }