用于BGL图的简单循环移除算法

2 回答

• 0

  提升很棒 . 它有一个接受访问者的 depth_first_search 方法 . You can see more information about it here .

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

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

  当然记住后边缘是关闭图中循环的边缘 .

  回复于 2024-04-20T15:27:48+08:00
• 5

  正如你所说，这是一个简单的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
  

  回复于 2024-04-20T15:27:48+08:00