当前位置：文江博客话题详情

BGL 图的简单循环消除算法

发布于 2024-10-14 17:13:16 字数 130 浏览 4 评论 0原文

我的问题应该很简单，给定一个图（BGL adjacency_list），是否有一个简单的算法来删除循环？我的第一次尝试是使用 DFS 访问者来检测关闭循环的边缘，然后将其删除，但我无法正确实现它。

有什么建议吗？代码示例是最好的。

原文

分享到QQ

分享到微博

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

发布评论

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

沉默的熊 2024-10-21 17:13:16

提升很棒。它有一个接受访问者的 depth_first_search 方法。您可以在此处查看有关它的更多信息。

您需要做的就是实现这样的访问者：

class CycleTerminator : public boost::dfs_visitor<> {
    template <class Edge, class Graph>
    void back_edge(Edge e, Graph& g) {
        //implement
    }
};

当然要记住后边是图中闭合循环的边。

Boost is great. It has a depth_first_search method that accepts a visitor. You can see more information about it here.

All you need to do is implement a visitor like this:

class CycleTerminator : public boost::dfs_visitor<> {
    template <class Edge, class Graph>
    void back_edge(Edge e, Graph& g) {
        //implement
    }
};

remembering of course that a back edge is an edge that closes a cycle in the graph.

回复收藏 0 原文

只有一腔孤勇 2024-10-21 17:13:16

正如你所说，这是一个简单的 DFS。每次来到之前访问过的节点，都会有一个循环。只需删除最后一个边缘即可。

没有特定语言的伪代码。

void walk(current_node, previous_node)
   if visited[current_node]
      remove edge between current_node and previous_node
      return
   end

   visited[current_node] = true
   for (each adjacent node) 
      walk(adjacent_node, current_node)
   end
end

It's a simple DFS, as you said. Each time you come to a node you visited before, there's a cycle. Just remove the last edge.

A pseudocode in no particular language.

void walk(current_node, previous_node)
   if visited[current_node]
      remove edge between current_node and previous_node
      return
   end

   visited[current_node] = true
   for (each adjacent node) 
      walk(adjacent_node, current_node)
   end
end

回复收藏 0 原文

~没有更多了~