Boost Graph Library - 有向图的最小生成树-Java 学习之路

我有一个问题，需要我在Boost图库中找到有向图的最小生成树 .

我的第一次尝试是使用深度优先搜索和DFS访问者 . 我的计划是忽略除树边回调之外的所有边 . 这不起作用，我在下面举例说明原因 .

我的问题是，如果我可以让我的dfs-visitor在BGL中创建有向图的最小生成树 .

它有算法，这里已经讨论过（Finding a minimum spanning tree on a directed graph）我可以为BGL实现't tell if it'或者它已经在BGL中实现了's just a simple modification of something that' .

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/depth_first_search.hpp>


struct my_visitor : public boost::dfs_visitor<>
{
    template <class Edge, class Graph>
    void back_edge(Edge e, const Graph&) 
    {
        std::cout << "Back edge: " << e << std::endl;
    }

    template <class Edge, class Graph>
    void forward_or_cross_edge(Edge u, const Graph& g)
    {
        std::cout << "Forward or cross edge: " << u << std::endl;
    }

    template <class Edge, class Graph>
    void tree_edge(Edge u, const Graph& g)
    {
        std::cout << "Tree Edge: " << u << std::endl;
    }
};


int main()
{
    using namespace boost;

    typedef boost::adjacency_list< listS, vecS, bidirectionalS > digraph;

    // Construct the directed graph
    digraph g(2);

    add_edge(1, 0, g);
    //add_edge(0, 1, g);

    my_visitor vis2;
    boost::depth_first_search(g, visitor(vis2));

    return 0;
}

这是失败的例子 . 如果我有以下有向图

digraph G {
0;
1;
1->0 ;
}

深入第一次搜索dfs-visitor，1-> 0被归类为前沿 .

如果更改了图形以使边缘为0-> 1，则它是树边缘 .

从前向边缘的严格定义和DFS的源代码，由于顶点0在顶点1之前被访问，因此它是前沿 .

但是，边缘1-> 0在技术意义上仍然是树边缘，并且从其页面中给出的定义为http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/graph_theory_review.html .

前沿是非树边（u，v），它将顶点u连接到搜索树中的后代v .

那么，BGL中是否有一个简单的解决方案，还是我必须为它实现BGL中的一种算法？

2 回答

0

正如您可能已经知道的那样，您正在处理的问题是在我们处理有向图时搜索最小权重的跨越树状结构 . 树状结构是具有指定的根顶点 r 的图形，使得所有其他顶点可以从 r 到达，即，存在从图中的 r 到所有其他顶点的路径 .

不幸的是，Boost Graph Library中没有解决这个问题的算法，所以你需要使用像这样的第三方实现one或者自己实现一个 . 上面给出的实现（通过atofigh在github.com上）使用Edmond's algorithm，这是一种用于解决跨越树突问题的流行算法 .

请记住，像Kruskal 's algorithm or Prim' s算法这样的算法不能在有向图上工作，因为cut属性不能用于有向图 .

回复于 2024-04-28T19:57:17+08:00

我最终使用了here的Edmonds算法 . 感谢HueHang但我在收到你的答复之前最终找到了算法并使用它 . 这个问题在大约3周内仍未得到答复 .

这是我使用edmonds_optimum_branching.hpp的简单测试程序 .

#include <iostream>
#include <vector>
#include <utility>
#include <iterator>
#include <cerrno>
#include <boost/concept_check.hpp>
#include <boost/operators.hpp>
#include <boost/multi_array.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_concepts.hpp>

#include "edmonds_optimum_branching.hpp"

typedef boost::property<boost::edge_weight_t, double>       EdgeProperty;
typedef boost::adjacency_list<boost::listS,
                              boost::vecS,
                              boost::directedS,
                              boost::no_property,
                              EdgeProperty>                 Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor       Vertex;
typedef boost::graph_traits<Graph>::edge_descriptor         Edge;

void main()
{
    const int N = 3;
    Graph G(N);

    std::vector<Vertex> the_vertices;
    BOOST_FOREACH (Vertex v, vertices(G))
        the_vertices.push_back(v);

    add_edge(the_vertices[0], the_vertices[2], 1.0, G);
    add_edge(the_vertices[2], the_vertices[1], 1.0, G);
    add_edge(the_vertices[1], the_vertices[0], 1.0, G);

    std::vector<Edge> branching;
    edmonds_optimum_branching<true, false, false>(G,
        get(boost::vertex_index_t(), G),
        get(boost::edge_weight_t(), G),
        static_cast<Vertex *>(0),
        static_cast<Vertex *>(0),
        std::back_inserter(branching));

    for each (Edge e in branching)
        std::cout << "(" << boost::source(e, G) << ", " << boost::target(e, G) << ")\t" << std::endl;
}

当运行示例代码时，我得到正确的答案为（2,1）和（0,2） .

算法返回最佳分支的边缘 . 它还具有加权边，可以找到最小或最大权重树 . 我只是使用权重1，如上例所示，因为我不需要加权图 . 它也可以选择树根的根 .

回复于 2024-04-28T19:57:17+08:00

Boost Graph Library - 有向图的最小生成树

2 回答

相关问题