スタックベースのDFSを使用した有向グラフでのサイクル検出

Question

スタックオーバーフローの例外が発生した後、algoが失敗しています。 Directed Graphでサイクル検出のために修正する方法を教えてください。可能であれば、再帰の代わりにスタックに基づいてalgoを提供することもできます。

public boolean hasCycle(Graphnode<T> n) { 

    n.setMark(IN_PROGRESS); 

    for (Graphnode<T> m : n.getSuccessors()) { 
     if (m.getMark() == IN_PROGRESS) { 
      return true; 
     } 

     if (m.getMark() != DONE) { 
      if (hasCycle(m)) { 
       return true; 
       } 
     } 
    } 

    n.setMark(DONE); 

    return false; 
} 

おかげで、 Vikrant

Answer 1

は、私は長い時間のためのもののこの種を行っていないが、あなたのコードは奇妙なようです。 あなたの最初のifの条件は以下のとおりです。

if (m.getMark() == IN_PROGRESS) { 

return true; 
} 

は、私はそれが代わりにこれをすべきだと思います。

if (m.getMark() == IN_DONE) { 

return true; 
} 

ない場合は、m.getMark() == IN_PROGRESSとm.getMark() != DONEの違いは何ですか？ 2番目のif-conditionは決して引き起こされません。

注：DFSまたはスタックを使用する多くのアルゴリズムが見つかります。