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.

// 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 Books in C++ Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - C++ Program to Check if a Directed Graph is Strongly or Weakly Connected

» Next - C++ Program to Implement Dijkstra’s Algorithm using Set

Related Posts:

Recommended Articles: