Boost图库-有向图的最小生成树

Question

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

我的第一个尝试是使用深度优先搜索和dfs-visitor。我的计划是忽略除树边回调之外的所有边。这不起作用，我给出了下面的例子来说明原因。

我的问题是我是否可以让我的dfs-visitor在BGL中创建一个有向图的最小生成树。

#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，那么它就是树边。

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

Answer 1

你们所处理的问题是，你们可能已经知道，像我们处理有向图一样，寻找一个最小权的生成树状图。树状图是具有指定的根顶点R的图，使得所有其他顶点都可以从R到达，即存在从R到图中所有其他顶点的路径。

不幸的是，Boost图库中没有解决这个问题的算法，所以您需要使用像这样的第三方实现或者自己实现。上面给出的实现（由atofigh在github.com上）使用了Edmond的算法，这是一种流行的求解生成树形问题的算法。

请记住，像Kruskal算法或Prim算法这样的算法对有向图不起作用，因为割性质对有向图不起作用。