有向グラフ内に存在するサイクルでノードを出力する

Question

DFSアルゴリズムを使用してサイクルを検出できることは理解していますが、バックエッジhttp://cs.wellesley.edu/~cs231/fall01/dfs.pdfを検出してください。私は、上記の方法に従うと同時に、効率的で「クリーン」な方法でノードをノードに出力する方法を理解することができません。

は、これは私が自分自身の実装でそれをやった方法です

おかげ

Answer 1

いくつかの助けのためにgratfeullだろう。あなたのPDFで使用されている命名規則と少し違うが、それが何をするのかははっきりしているはずです。 すべてm_*変数は、m_topoOrderとm_cycleを除き、スタックです。 サイクルのノードはm_cycleになります。 m_onStackは、再帰呼び出しスタック上にあるノードを追跡します。

完全な説明については、Robert SedgewickのAlgorithmsをお読みください。

void QxDigraph::dfs(int v) 
{ 
    m_marked[v] = true; 
    m_onStack[v] = true; 

    foreach(int w, m_adj[v]) { 
     if(hasCycle()) return; 
     else if(!m_marked[w]) 
     { 
      m_edgeTo[w] = v; 
      dfs(w); 
     } 
     else if(m_onStack[w]) 
     { 
      m_cycle.clear(); 
      for(int x=v; x!=w; x = m_edgeTo[x]) 
       m_cycle.push(x); 
      m_cycle.push(w); 
      m_cycle.push(v); 
     } 
    } 
    m_onStack[v] = false; 
    m_topoOrder.push(v); 
}