cycle - 输出有向图中存在的循环中的节点

Question

虽然我知道我们可以通过检测后端http://cs.wellesley.edu/~cs231/fall01/dfs.pdf来使用 DFS 算法检测周期。在遵循上述方法时，我无法弄清楚如何以有效和“干净”的方式输出循环中的节点。

将不胜感激一些帮助

谢谢

Answer 1

这就是我在自己的实现中所做的。它的命名约定与您的 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);
}