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>usingnamespacestd;
classGraph {int V; // No. of vertices// Pointer to an array containing adjacency listslist<int>* adj;
// A function used by DFSvoidDFS_Connect_Comp(int v, bool visited[]);
public:
Graph(int V); // Constructor
~Graph();
voidaddEdge(int v, int u);
voidconnectedComponents();
};
void Graph::connectedComponents()
{
// Mark all the vertices as not visitedbool* visited = newbool[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 = newlist<int>[V];
}
Graph::~Graph() { delete[] adj; }
// method to add an undirected edgevoid Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v);
}
// Driver codeintmain(){
// Create a graph given in the above diagramint 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();
return0;
}
Comments