C++ Program to Find the Vertex Connectivity of a Graph

«
»
This is a C++ Program to find vertex connectivity of a graph. A vertex in an undirected connected graph is an articulation point (or cut vertex) iff removing it (and edges through it) disconnects the graph. Articulation points represent vulnerabilities in a connected network – single points whose failure would split the network into 2 or more disconnected components. They are useful for designing reliable networks

Here is source code of the C++ Program to Find the Vertex 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 articulation points 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 APUtil(int v, bool visited[], int disc[], int low[], int parent[],
  13.                 bool ap[]);
  14.     public:
  15.         Graph(int V); // Constructor
  16.         void addEdge(int v, int w); // function to add an edge to graph
  17.         void AP(); // prints articulation points
  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. // A recursive function that find articulation points using DFS traversal
  33. // u --> The vertex to be visited next
  34. // visited[] --> keeps tract of visited vertices
  35. // disc[] --> Stores discovery times of visited vertices
  36. // parent[] --> Stores parent vertices in DFS tree
  37. // ap[] --> Store articulation points
  38. void Graph::APUtil(int u, bool visited[], int disc[], int low[], int parent[],
  39.         bool ap[])
  40. {
  41.     // A static variable is used for simplicity, we can avoid use of static
  42.     // variable by passing a pointer.
  43.     static int time = 0;
  44.  
  45.     // Count of children in DFS Tree
  46.     int children = 0;
  47.  
  48.     // Mark the current node as visited
  49.     visited[u] = true;
  50.  
  51.     // Initialize discovery time and low value
  52.     disc[u] = low[u] = ++time;
  53.  
  54.     // Go through all vertices aadjacent to this
  55.     list<int>::iterator i;
  56.     for (i = adj[u].begin(); i != adj[u].end(); ++i)
  57.     {
  58.         int v = *i; // v is current adjacent of u
  59.  
  60.         // If v is not visited yet, then make it a child of u
  61.         // in DFS tree and recur for it
  62.         if (!visited[v])
  63.         {
  64.             children++;
  65.             parent[v] = u;
  66.             APUtil(v, visited, disc, low, parent, ap);
  67.  
  68.             // Check if the subtree rooted with v has a connection to
  69.             // one of the ancestors of u
  70.             low[u] = min(low[u], low[v]);
  71.  
  72.             // u is an articulation point in following cases
  73.  
  74.             // (1) u is root of DFS tree and has two or more chilren.
  75.             if (parent[u] == NIL && children > 1)
  76.                 ap[u] = true;
  77.  
  78.             // (2) If u is not root and low value of one of its child is more
  79.             // than discovery value of u.
  80.             if (parent[u] != NIL && low[v] >= disc[u])
  81.                 ap[u] = true;
  82.         }
  83.  
  84.         // Update low value of u for parent function calls.
  85.         else if (v != parent[u])
  86.             low[u] = min(low[u], disc[v]);
  87.     }
  88. }
  89.  
  90. // The function to do DFS traversal. It uses recursive function APUtil()
  91. void Graph::AP()
  92. {
  93.     // Mark all the vertices as not visited
  94.     bool *visited = new bool[V];
  95.     int *disc = new int[V];
  96.     int *low = new int[V];
  97.     int *parent = new int[V];
  98.     bool *ap = new bool[V]; // To store articulation points
  99.  
  100.     // Initialize parent and visited, and ap(articulation point) arrays
  101.     for (int i = 0; i < V; i++)
  102.     {
  103.         parent[i] = NIL;
  104.         visited[i] = false;
  105.         ap[i] = false;
  106.     }
  107.  
  108.     // Call the recursive helper function to find articulation points
  109.     // in DFS tree rooted with vertex 'i'
  110.     for (int i = 0; i < V; i++)
  111.         if (visited[i] == false)
  112.             APUtil(i, visited, disc, low, parent, ap);
  113.  
  114.     // Now ap[] contains articulation points, print them
  115.     for (int i = 0; i < V; i++)
  116.         if (ap[i] == true)
  117.             cout << i << " ";
  118. }
  119.  
  120. // Driver program to test above function
  121. int main()
  122. {
  123.     // Create graphs given in above diagrams
  124.     cout << "\nArticulation points in first graph \n";
  125.     Graph g1(5);
  126.     g1.addEdge(1, 0);
  127.     g1.addEdge(0, 2);
  128.     g1.addEdge(2, 1);
  129.     g1.addEdge(0, 3);
  130.     g1.addEdge(3, 4);
  131.     g1.AP();
  132.  
  133.     cout << "\nArticulation points in second graph \n";
  134.     Graph g2(4);
  135.     g2.addEdge(0, 1);
  136.     g2.addEdge(1, 2);
  137.     g2.addEdge(2, 3);
  138.     g2.AP();
  139.  
  140.     cout << "\nArticulation points in third graph \n";
  141.     Graph g3(7);
  142.     g3.addEdge(0, 1);
  143.     g3.addEdge(1, 2);
  144.     g3.addEdge(2, 0);
  145.     g3.addEdge(1, 3);
  146.     g3.addEdge(1, 4);
  147.     g3.addEdge(1, 6);
  148.     g3.addEdge(3, 5);
  149.     g3.addEdge(4, 5);
  150.     g3.AP();
  151.  
  152.     return 0;
  153. }

Output:

advertisement
$ g++ VertexConnectivity.cpp
$ a.out
 
 
Articulation points in first graph 
0 3 
Articulation points in second graph 
1 2 
Articulation points in third graph 
1 
------------------
(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