connected components in an undirected graph in c++

Question

I was searching for a c++ code to find connected components in an undirected graph. I have a big matrix which is called "directed". Its elements are zero or one. directed(i,j)=1 means i vertice has a directed link to j vertice. I want to find the number of different groups created by directly or indirectly connection of vertices and size of the groups. Below code takes connected vertices and print different groups' elements in different lines. Knowing directed matrix, could anyone help me to find the number of groups and size of each of them? This is the code:

// C++ program to print connected components in
// an undirected graph
#include<iostream>
#include <list>
using namespace std;

// Graph class represents a undirected graph
// using adjacency list representation
int input(istream& in=cin)
{
int x;
in >> x;
return x;
}


class Graph
{
int V;    // No. of vertices

// Pointer to an array containing adjacency lists
list<int> *adj;

// A function used by DFS
void DFSUtil(int v, bool visited[]);
public:
Graph(int V);   // Constructor
void addEdge(int v, int w);
void connectedComponents();
};

// Method to print connected components in an
// undirected graph
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
        DFSUtil(v, visited);

        cout << "\n";
       }
    }
}

void Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
cout << v << " ";

// Recur for all the vertices
// adjacent to this vertex
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
    if(!visited[*i])
        DFSUtil(*i, visited);
}

Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}

// method to add an undirected edge
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v);
}

// Drive program to test above
int main()
{
int directed[2][2];

 directed[0][0]=1;
 directed[0][1]=0;
 directed[0][2]=0;
 directed[1][1]=1;
 directed[1][0]=1;
 directed[1][2]=1;
 directed[2][1]=0;
 directed[2][2]=0;
 directed[2][0]=1;
 return 0;
 }

Answer 1

Could you please provide a runnable answer (x4)

Sure:

Live On Coliru

// C++ program to print connected components in
// an undirected graph
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>

// Graph class represents a undirected graph
// using adjacency list representation
class Graph {
    using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
    using Component = int;
    using Mapping = std::map<G::vertex_descriptor, Component>;
    G g;

  public:
    Graph(int V) : g(V) {}
    void addEdge(int v, int w);
    void connectedComponents();
};

// Method to print connected components in an
// undirected graph
void Graph::connectedComponents() {
    Mapping mappings;
    int n = boost::connected_components(g, boost::make_assoc_property_map(mappings));

    for (Component c = 0; c<n; ++c) {
        std::cout << "component " << c << ":";

        for (auto& mapping : mappings)
            if (mapping.second == c) std::cout << " " << mapping.first;

        std::cout << "\n";
    }
}

void Graph::addEdge(int v, int w) {
    boost::add_edge(v, w, g);
}

int main() {
    // Create a graph given in the above diagram
    Graph g(5); // 5 vertices numbered from 0 to 4
    g.addEdge(1, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 4);

    std::cout << "Following are connected components \n";
    g.connectedComponents();
}

Prints

Following are connected components 
component 0: 0 1
component 1: 2 3 4

Answer 2

Modify the DFSUtil methord to return an int the specifies the number of nodes visited.

int Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
int count  = 0;
cout << v << " ";

// Recur for all the vertices
// adjacent to this vertex
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
    if(!visited[*i])
      count += DFSUtil(*i, visited, count + 1);
    else 
      return 1;
return count;
}

And with some booking keeping we'll know know many groups and the size of each group from this

   // Method to print connected components in an
    // undirected graph
    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;
    vector<pair<int,int>> groups;
    for (int v=0; v<V; v++)
    {
         if (visited[v] == false)
           {
            // print all reachable vertices
            // from v
            int groupSize = DFSUtil(v, visited);
            groups.push_back(make_pair(v, groupSize))
            cout << "\n";
           }
        }
    }