C++ program to find connected components of a graph














































C++ program to find connected components of a graph




Connected components in a graph refer to a set of vertices that are connected to each other by direct or indirect paths. In other words, a set of vertices in a graph is a connected component if every node in the graph can be reached from every other node in the graph. Algorithm: step-1 Mark all vertices as non visited step-2 Select any vertex (say V). step-3 If V is not visited , i) call function DFS_Connect_Comp ( V ) ii) print new line character. step-4 If V is visited, Go to step-2 and choose another vertex. DFS_Connect_Comp ( V ) step-1 Mark V as visited. step-2 Print V step-3 Do following for every adjacent vertex 'U' of 'V' If U is not visited, call recursively for DFS_Connect_Comp( U ). C++ implementation of the above Algorithm

#include<bits/stdc++.h>
using namespace std; class Graph { int V; // No. of vertices // Pointer to an array containing adjacency lists list<int>* adj; // A function used by DFS void DFS_Connect_Comp(int v, bool visited[]); public: Graph(int V); // Constructor ~Graph(); void addEdge(int v, int u); void connectedComponents(); }; void Graph::connectedComponents() { // Mark all the vertices as not visited bool* visited = new bool[V]; for (int v = 0; v < V; v++) visited[v] = false; for (int v = 0; v < V; v++) { if (visited[v] == false) { // print all reachable vertices // from v DFS_Connect_Comp(v, visited); cout << "\n"; } } delete[] visited; } void Graph::DFS_Connect_Comp(int v, bool visited[]) { visited[v] = true; cout << v << " "; list<int>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i]) DFS_Connect_Comp(*i, visited); } Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } Graph::~Graph() { delete[] adj; } // method to add an undirected edge void Graph::addEdge(int v, int w) { adj[v].push_back(w); adj[w].push_back(v); } // Driver code int main() { // Create a graph given in the above diagram int n; cout<<"Enter no.of vertices\n"; cin>>n; Graph g(n); char choice='Y'; while(choice=='Y' || choice=='y'){ int v,u; cout<<"Enter vertices of an edge\n"; cin>>v>>u; g.addEdge(v, u); cout<<"Want to add another edge?\n"; cout<<"If yes press 'Y' otherwise press any key\n"; cin>>choice; } cout << "Following are connected components \n"; g.connectedComponents(); return 0; }
Output :

Enter no.of vertices
5

Enter vertices of a edge
0 1

Want to add another edge?
If yes press 'Y' otherwise press any key
Y

Enter vertices of a edge
2 3

Want to add another edge?
If yes press 'Y' otherwise press any key
Y

Enter vertices of a edge
3 4

Want to add another edge?
If yes press 'Y' otherwise press any key
N


Following are connected components 
0 1
2 3 4

Comments