C++ program to find connected components of a graph
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