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.

advertisement
advertisement

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

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!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter