Простой алгоритм удаления цикла для графа BGL

Question

Моя проблема должна быть довольно простой, учитывая график (BGL adjacency_list), есть ли простой алгоритм для удаления циклов?Моей первой попыткой было использование посетителя DFS, чтобы обнаружить ребро, которое закроет цикл, а затем удалить его, но я не смог правильно его реализовать.

Есть предложения?Образцы кода будут лучше.

Answer 1

Повышение это здорово. У него есть метод depth_first_search, который принимает посетителя. Подробнее об этом можно прочитать здесь .

Все, что вам нужно сделать, это реализовать посетителя следующим образом:

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

помня, конечно, что задний край - это край, который замыкает цикл на графике.

Answer 2

Как вы сказали, это простая 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