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

我有一个问题，要求我在 Boost Graph Library 中找到有向图的最小生成树。

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

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

它有一些算法并且已经在这里讨论过（在有向图上寻找最小生成树 https://stackoverflow.com/questions/21991823/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-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 http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/graph_theory_review.html.

前向边是将顶点 u 连接到 a 的非树边 (u,v) 搜索树中的后代 v。

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

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

不幸的是，Boost Graph Library 中没有算法可以解决这个问题，所以你需要使用像这样的第三方实现one https://github.com/atofigh/edmonds-alg或者自己实施一个。上面给出的实现（由 atofigh 在 github.com 上）使用埃德蒙算法 https://en.wikipedia.org/wiki/Edmonds'_algorithm，这是解决跨越树状问题的流行算法。

请记住，像 Kruskal 算法或 Prim 算法这样的算法不适用于有向图，因为削减财产不处理有向图。