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.

`// A C++ program to find articulation points 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 APUtil(int v, bool visited[], int disc[], int low[], int parent[],

bool ap[]);

public:

Graph(int V); // Constructor

void addEdge(int v, int w); // function to add an edge to graph

void AP(); // prints articulation points

};

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

`}`

`// A recursive function that find articulation points using DFS traversal`

`// u --> The vertex to be visited next`

`// visited[] --> keeps tract of visited vertices`

`// disc[] --> Stores discovery times of visited vertices`

`// parent[] --> Stores parent vertices in DFS tree`

`// ap[] --> Store articulation points`

void Graph::APUtil(int u, bool visited[], int disc[], int low[], int parent[],

bool ap[])

`{`

`// A static variable is used for simplicity, we can avoid use of static`

`// variable by passing a pointer.`

static int time = 0;

`// Count of children in DFS Tree`

int children = 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 make it a child of u`

`// in DFS tree and recur for it`

if (!visited[v])

`{`

children++;

parent[v] = u;

APUtil(v, visited, disc, low, parent, ap);

`// Check if the subtree rooted with v has a connection to`

`// one of the ancestors of u`

low[u] = min(low[u], low[v]);

`// u is an articulation point in following cases`

`// (1) u is root of DFS tree and has two or more chilren.`

if (parent[u] == NIL && children > 1)

ap[u] = true;

`// (2) If u is not root and low value of one of its child is more`

`// than discovery value of u.`

if (parent[u] != NIL && low[v] >= disc[u])

ap[u] = true;

`}`

`// Update low value of u for parent function calls.`

else if (v != parent[u])

low[u] = min(low[u], disc[v]);

`}`

`}`

`// The function to do DFS traversal. It uses recursive function APUtil()`

void Graph::AP()

`{`

`// 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];

bool *ap = new bool[V]; // To store articulation points

`// Initialize parent and visited, and ap(articulation point) arrays`

for (int i = 0; i < V; i++)

`{`

parent[i] = NIL;

visited[i] = false;

ap[i] = false;

`}`

`// Call the recursive helper function to find articulation points`

`// in DFS tree rooted with vertex 'i'`

for (int i = 0; i < V; i++)

if (visited[i] == false)

APUtil(i, visited, disc, low, parent, ap);

`// Now ap[] contains articulation points, print them`

for (int i = 0; i < V; i++)

if (ap[i] == true)

cout << i << " ";

`}`

`// Driver program to test above function`

int main()

`{`

`// Create graphs given in above diagrams`

cout << "\nArticulation points 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.AP();

cout << "\nArticulation points in second graph \n";

Graph g2(4);

g2.addEdge(0, 1);

g2.addEdge(1, 2);

g2.addEdge(2, 3);

g2.AP();

cout << "\nArticulation points 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.AP();

return 0;

`}`

Output:

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

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