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

我有一个问题需要在Boost图库中找到有向图的最小生成树。
我的第一个尝试是使用深度优先搜索和dfs访问者。我的计划是忽略除树边回调之外的所有边。这不起作用，我给出下面的例子说明原因。
我的问题是我是否可以让我的dfs访问者在bgl中创建有向图的最小生成树。
它有算法，这里已经讨论过了（Finding a minimum spanning tree on a directed graph），我不知道它是不是为bgl实现的，或者它只是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访问者时，1->0被分类为前边缘。
如果图形更改为边为0->1，则它是树边。
从DFS的前向边的严格定义和源代码来看，由于顶点0是在顶点1之前访问的，所以它是前向边。
然而，edge 1->0仍然是一个技术意义上的树边缘，从页面中定义为http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/graph_theory_review.html。
前向边是将顶点u连接到
搜索树中的后代v。
那么，bgl中是否有一个简单的解决方案，或者我必须实现bgl中的一个算法来实现它？

最佳答案

你要处理的问题是，正如你可能已经知道的，当我们处理有向图时，寻找最小权重的生成树形图。树形图是一个具有指定根顶点的曲线图，使得所有其他顶点都可以从r中获得，即存在从图中的“c>”到所有其他顶点的路径。
不幸的是，Boost图形库中没有解决此问题的算法，因此您需要使用像这样的第三方实现one或自己实现一个上面给出的实现（通过github.com上的atofigh）使用了Edmond's algorithm，这是一种解决生成树形图问题的流行算法。
请记住，像kruskal算法或prim算法这样的算法不适用于有向图，因为cut属性不适用于有向图。

关于algorithm - Boost图形库-有向图的最小生成树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37836334/