2

こんにちは皆さん、幅優先探索アルゴリズムを使用して、グラフ(隣接行列)の関数を作成して、接続されたコンポーネントの数を返します。

ほぼ正常に動作します。コンポーネントの数が頂点の数と等しい場合は適切な値を返しますが、コンポーネントの数が頂点の数よりも小さい場合は、(適切な値 +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) に入れると、コンポーネントの数 = 頂点の数であるグラフを除くすべてのグラフに適切な値が与えられます (この値は「適切な値-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;
 }
4

1 に答える 1

1 
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 には隣人がいる可能性があります。

于 2012-11-03T21:21:46.483 に答える