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

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

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

Спасибо


cycle graph-algorithm depth-first-search
person Lipika Deka    schedule 30.07.2011    source источник
comment
Немного проверил и похоже: как только мы сталкиваемся с серым узлом и следуем всем серым узлам от него к первому, мы получаем узлы цикла   -  person Lipika Deka    schedule 30.07.2011

Ответы (1)


arrow_upward
0
arrow_downward

Вот как я сделал это в своей собственной реализации. Он немного отличается в соглашениях об именах от того, который используется в вашем 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);
}
person pokey909    schedule 02.08.2011