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

Question

バックエッジhttp://cs.wellesley.edu/~cs231/fall01/dfs.pdfを検出することにより、DFS アルゴリズムでサイクルを検出できることは理解しています。上記の方法に従っている間、サイクル内のノードを効率的かつ「クリーン」な方法で出力する方法を理解できません。

いくつかの助けに感謝します

ありがとう

Answer 1

これは、私が自分の実装でそれを行った方法です。PDF で使用されているものとは命名規則が少し異なりますが、それが何をするのかは明らかなはずです。スタックであるとを除いて、すべてのm_*変数はベクトルです。サイクルのノードは になります。は、再帰呼び出しスタックにあるノードを追跡します。m_topoOrderm_cyclem_cyclem_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);
}