Hi guys so I am making function for my graphs (adjacency matrices) to return number of connected components using breadth first search algorithm.

It almost works properly. It returns proper value if number of components is equal to number of vertices, but if number of components is smaller than number of vertices it returns (proper value +1). I have no idea how to fix it, so if you could give it a look and tell me I would be glad

``````int Graph::getNumberOfConnectedComponents()
{
int components=0;
queue<int> S;
int n = getVerticesCount();//as name indicates it returns number of vertices in graph
bool* visited = new bool[n];
for(int i=1;i<n;i++)
visited[i]=false;
visited[0]=true;

S.push(0);
while(!S.empty())
{
int v = S.front();
S.pop();
list<int> x = getNeighbors(v);//as name indicates this function returns list of neighbours of given vertice
if(!x.empty())
{
list<int>::iterator it;
for (it=x.begin(); it!=x.end(); it++)
{
if(visited[*it]==false)
{
S.push(*it);
visited[*it]=true;
}
}
}

if(S.empty())
{
components++;
for(int i=1;i<n;i++)
{
if(visited[i]==false)
{
S.push(i);
visited[i]=true;
break;
}
}

}
}
return components;
}
``````

I explained what those functions do in comments, hope you will be able to help me :/ . Btw if you change place of components++; and put it into if(visited[i]==false) it gives proper value for all graphs except those which number of components = number of vertices (for those this value is "proper value-1").

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.