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

发布于 2024-11-27 02:28:06 字数 238 浏览 1 评论 0原文

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

如果您能提供一些帮助，我们将不胜感激

，谢谢

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

﹉夏雨初晴づ 2024-12-04 02:28:06

这就是我在自己的实现中所做的。它的命名约定与 PDF 中使用的命名约定略有不同，但它的作用应该很明显。
所有 m_* 变量都是向量，除了 m_topoOrder 和 m_cycle 是堆栈。
循环的节点将在m_cycle中。
m_onStack 跟踪递归调用堆栈上的节点。

对于完整的描述，我建议阅读 Robert Sedgewick 所著的《算法》一书。

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

This is how i did it in my own implementation. It deviates a little bit in the naming conventions from the one used in your PDF but it should be obvious what it does.
All m_* variables are vectors, except m_topoOrder and m_cycle which are stacks.
The nodes of the cycle will be in m_cycle.
The m_onStack keeps track of nodes which are on the recursive call stack.

For a complete description i suggest the book Algorithms by Robert Sedgewick.

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

回复收藏 0 原文

~没有更多了~