Выведите узлы в цикле, существующем в ориентированном графе

Question

Хотя я понимаю, что мы можем обнаруживать циклы с помощью алгоритма DFS, обнаруживая back-edge http://cs.wellesley.edu/~cs231/fall01/dfs.pdf. Я не могу понять, как выводить узлы в цикле эффективным и «чистым» способомследуя вышеуказанному методу.

Буду благодарен за помощь

Спасибо

Answer 1

Вот как я это сделал в своей собственной реализации. Он несколько отклоняется в соглашениях об именах от того, который используется в вашем PDF, но должно быть очевидно, что он делает. Все переменные m_* являются векторами, кроме m_topoOrder и m_cycle, которые являются стеками. Узлы цикла будут в m_cycle. m_onStack отслеживает узлы, которые находятся в стеке рекурсивных вызовов.

Для полного описания предлагаю книгу «Алгоритмы» Роберта Седжвика.

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);
}