1

グラフのサイクルでノードの数を見つけようとしています。再帰と DFS を使用して、グラフのすべてのサイクルのノード数を計算しています。C++ の計算関数は次のとおりです。

int iscyclic(int node,bool visited[],bool rec[],vector<int>g[])
{
    if(!visited[node])
{
    visited[node] = true;
    rec[node] = true;
    vector<int>::iterator it;
    for(it=g[node].begin();it!=g[node].end();it++)
    {
        if(!visited[*it] && iscyclic(*it,visited,rec,g))
        {
            kount++;
        }
        else if(rec[*it])
            kount++;
    }
}
rec[node] = false;
return kount;
}

および配列はデフォルトVisitedでrecfalse にkount設定されており、グローバルに として設定されてい0ます。はkount、有向グラフの1サイクルのノード数を計算することになっていますが、答えが間違っている場合があります。助けてください。最近グラフ理論を学び始めました。

4

1 に答える 1

0

これを行うべきではありません：

else if(rec[*it])
   kount++;

また、開始ノード (関数を呼び出すノード) が実際にサイクルの一部であることを確認する必要があります。

3 番目のこと -実際に戻る必要がある場合、またはこの分岐でサイクルに遭遇したかどうかに基づいて、関数kcountの結果として戻ります。truefalse

于 2016-08-07T08:20:35.263 に答える