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 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.