5

この質問は、このフォーラムやインターネットの他の場所で何度も聞かれていることを知っています。しかし、爪を伸ばして私を攻撃する前に、我慢してください。

私は初心者学習グラフです。私の演習の一環として、ここで Graph クラスにメソッド hasCycle() を追加するように指定されています http://homepage.cs.uiowa.edu/~sriram/21/fall05/ExamplePrograms/ReaderFiles/Chap13/dfs/dfs.java .

私のアプローチは、こちらのフォーラムで提案されているように DFS を実行しています。

しかし、最初のリンクで既存の dfs メソッドを使用してこれを実装する方法に苦労しています。

これまでの私のアプローチは次のとおりです。

public boolean hasCycle(int start)
{
    vertexList[start].wasVisited = true;
    for(int j = 0; j < MAX_VERTS; j++)
    {  
        if(adjMat[start][j]==1 && vertexList[j].wasVisited==true)
        return true;
        else if(adjMat[start][j]==1 && vertexList[j].wasVisited==false)
        {
         vertexList[start].wasVisited == true;
         hasCycle(j);
        }
    }
   return false;
}

ここで 2 つの問題があります。1 つ目は、theGraph.dfs(); 行の代わりに DFSApp クラスで hasCycle() を呼び出すと、無限再帰に陥ります。第二に、宿題で必要な dfs() を使用していません。

ここで私が間違っていることに関して、正しい道への方向性は高く評価されます。

今のところ、dfs() を使用せずに、正しい個別の hasCycle() メソッドを実装することに集中しています。

4

1 に答える 1

10

注：この回答は、グラフが無向であることを前提としています（別の言い方をすれば、隣接行列は対称です）。有向グラフの場合、答えはより複雑になります。

への再帰呼び出しから返された値を確認する必要がありますhasCycle(j)。例えば：

if (hasCycle(j))
    return true;

これにより、サイクルにヒットして最上位レベルまで真を返す場合、「スタックが巻き戻されます」。

また、これはマイナーな点であり、機能には実際には影響しませんが、再帰呼び出しの前の行にhasCycle(j)はいくつかの問題があります。まず、二重ではなく単一の等号にする必要があります。hasCycle(j)第二に、再帰呼び出しで最初に発生することは、ノードjが訪問済みとしてマークされるため、実際には冗長です。

それを念頭に置いて、コードを簡略化します。

public boolean hasCycle(int start)
{
    vertexList[start].wasVisited = true;
    for (int j = 0; j < MAX_VERTS; j++) {  
        if (adjMat[start][j] == 1  &&  (vertexList[j].wasVisited  ||  hasCycle(j)))
            return true;
    }
    return false;
}

@mehrmoudiのコメントの後に編集：

わお。上記は完全に正しくありませんでした！ごめん！！以下の修正では、parentパラメーターを追加しました。

public boolean hasCycle(int start, int parent)
{
    vertexList[start].wasVisited = true;
    for (int j = 0; j < MAX_VERTS; j++) {  
        if (j != parent  &&  adjMat[start][j] == 1  &&  (vertexList[j].wasVisited  ||  hasCycle(j, start)))
            return true;
    }
    return false;
}
于 2013-10-29T06:24:57.763 に答える