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.

Here is source code of the C++ Program to Find the Edge Connectivity of a Graph. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. // A C++ program to find bridges in a given undirected graph
  2. #include<iostream>
  3. #include <list>
  4. #define NIL -1
  5. using namespace std;
  6.  
  7. // A class that represents an undirected graph
  8. class Graph
  9. {
  10.         int V; // No. of vertices
  11.         list<int> *adj; // A dynamic array of adjacency lists
  12.         void bridgeUtil(int v, bool visited[], int disc[], int low[],
  13.                 int parent[]);
  14.     public:
  15.         Graph(int V); // Constructor
  16.         void addEdge(int v, int w); // function to add an edge to graph
  17.         void bridge(); // prints all bridges
  18. };
  19.  
  20. Graph::Graph(int V)
  21. {
  22.     this->V = V;
  23.     adj = new list<int> [V];
  24. }
  25.  
  26. void Graph::addEdge(int v, int w)
  27. {
  28.     adj[v].push_back(w);
  29.     adj[w].push_back(v); // Note: the graph is undirected
  30. }
  31.  
  32. void Graph::bridgeUtil(int u, bool visited[], int disc[], int low[],
  33.         int parent[])
  34. {
  35.     // A static variable is used for simplicity, we can avoid use of static
  36.     // variable by passing a pointer.
  37.     static int time = 0;
  38.  
  39.     // Mark the current node as visited
  40.     visited[u] = true;
  41.  
  42.     // Initialize discovery time and low value
  43.     disc[u] = low[u] = ++time;
  44.  
  45.     // Go through all vertices aadjacent to this
  46.     list<int>::iterator i;
  47.     for (i = adj[u].begin(); i != adj[u].end(); ++i)
  48.     {
  49.         int v = *i; // v is current adjacent of u
  50.  
  51.         // If v is not visited yet, then recur for it
  52.         if (!visited[v])
  53.         {
  54.             parent[v] = u;
  55.             bridgeUtil(v, visited, disc, low, parent);
  56.  
  57.             // Check if the subtree rooted with v has a connection to
  58.             // one of the ancestors of u
  59.             low[u] = min(low[u], low[v]);
  60.  
  61.             // If the lowest vertex reachable from subtree under v is
  62.             // below u in DFS tree, then u-v is a bridge
  63.             if (low[v] > disc[u])
  64.                 cout << u << " " << v << endl;
  65.         }
  66.  
  67.         // Update low value of u for parent function calls.
  68.         else if (v != parent[u])
  69.             low[u] = min(low[u], disc[v]);
  70.     }
  71. }
  72.  
  73. // DFS based function to find all bridges. It uses recursive function bridgeUtil()
  74. void Graph::bridge()
  75. {
  76.     // Mark all the vertices as not visited
  77.     bool *visited = new bool[V];
  78.     int *disc = new int[V];
  79.     int *low = new int[V];
  80.     int *parent = new int[V];
  81.  
  82.     // Initialize parent and visited arrays
  83.     for (int i = 0; i < V; i++)
  84.     {
  85.         parent[i] = NIL;
  86.         visited[i] = false;
  87.     }
  88.  
  89.     // Call the recursive helper function to find Bridges
  90.     // in DFS tree rooted with vertex 'i'
  91.     for (int i = 0; i < V; i++)
  92.         if (visited[i] == false)
  93.             bridgeUtil(i, visited, disc, low, parent);
  94. }
  95.  
  96. // Driver program to test above function
  97. int main()
  98. {
  99.     // Create graphs given in above diagrams
  100.     cout << "\nBridges in first graph \n";
  101.     Graph g1(5);
  102.     g1.addEdge(1, 0);
  103.     g1.addEdge(0, 2);
  104.     g1.addEdge(2, 1);
  105.     g1.addEdge(0, 3);
  106.     g1.addEdge(3, 4);
  107.     g1.bridge();
  108.  
  109.     cout << "\nBridges in second graph \n";
  110.     Graph g2(4);
  111.     g2.addEdge(0, 1);
  112.     g2.addEdge(1, 2);
  113.     g2.addEdge(2, 3);
  114.     g2.bridge();
  115.  
  116.     cout << "\nBridges in third graph \n";
  117.     Graph g3(7);
  118.     g3.addEdge(0, 1);
  119.     g3.addEdge(1, 2);
  120.     g3.addEdge(2, 0);
  121.     g3.addEdge(1, 3);
  122.     g3.addEdge(1, 4);
  123.     g3.addEdge(1, 6);
  124.     g3.addEdge(3, 5);
  125.     g3.addEdge(4, 5);
  126.     g3.bridge();
  127.  
  128.     return 0;
  129. }

Output:

advertisement
$ g++ EdgeConnectivity.cpp
$ a.out
 
Bridges in first graph 
3 4
0 3
 
Bridges in second graph 
2 3
1 2
0 1
 
Bridges in third graph 
1 6
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.