Eclip7e 0 Newbie Poster

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 1.21 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.