CODEWITHSUNDEEP
c++matrixcomponents
MeIsNoob
MeIsNoob

Reputation: 69

C++ Finding number of connected components (BFS, adjacency matrix)

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. Heres the link to the code it looks more decent then the one below http://wklej.org/id/861341/

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").

@Edit 1 , here is this function john 

list<int> AdjacencyMatrixGraph::getNeighbors(int v)
 {
     list<int> x;
     if(v==0||v>=n)
     return x;

     for(int j=0;j<n;j++)
     {
     if(matrix[v][j]!=0)
         x.push_front(j);
     }
     return x;
 }

Upvotes: 2

Views: 4943

Answers (1)

john
john

Reputation: 88017

list<int> AdjacencyMatrixGraph::getNeighbors(int v)
 {
     list<int> x;
     if(v==0||v>=n)
     return x;

should be

list<int> AdjacencyMatrixGraph::getNeighbors(int v)
 {
     list<int> x;
     if(v<0||v>=n)
     return x;

vertex 0 can have neighbors as far as I can tell.

Upvotes: 1

Related Questions