c++ - C++查找已连接组件的数量(BFS，邻接矩阵)

嗨，大家好，我正在为我的图表(邻接矩阵)创建函数，以使用广度优先搜索算法返回连接组件的数量。

它几乎可以正常工作。如果分量数等于顶点数，它将返回适当的值，但是如果分量数小于顶点数，它将返回(适当的值+1)。我不知道如何解决它，因此，如果您可以看一下并告诉我，我将很高兴。继承人代码的链接，它看起来比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;
}

我在评论中解释了这些功能的作用，希望您能够对我有所帮助:/。顺便说一句，如果您更改组件的位置++；并将其放到if(visited [i] == false)中，它为所有图提供适当的值，但那些图的组成数=顶点数(对于该图，此值为“proper value-1”)。

@Edit 1，这是这个函数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;
 }

最佳答案

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

应该

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

据我所知，顶点0可以有邻居。