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

Question

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

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

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

它有一些算法，并且已经在这里讨论过（Finding a minispanning tree on a有向图），我无法判断它是否已针对 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。

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

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

Answer 1

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

不幸的是，Boost Graph Library 中没有算法可以解决这个问题，因此您需要使用像这样的第三方实现，或者自己实现一个。上面给出的实现（由 github.com 上的 atofigh 提供）使用Edmond 算法，这是解决跨越树状问题的流行算法。

请记住，像 Kruskal 算法或 Prim 算法这样的算法不适用于有向图，因为cut 属性不适用于有向图。