Boost Kruskal 最小生成树算法——无向图与有向图文档

Question

根据 documentation，boost 中实现的最小生成树算法应该只适用于无向图。然而，以下提供有向图作为算法输入的代码似乎工作正常：（在 MSVC Visual Studio 2019 上构建时，没有与 boost 相关的警告）

#include <boost/property_map/property_map.hpp>
#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <boost/graph/graph_utility.hpp>
using namespace boost;
typedef adjacency_list <vecS, vecS, directedS, no_property,
    property<edge_weight_t, double>>
    Graph_vvd_MST;
typedef adjacency_list_traits<vecS, vecS, directedS> Traits_vvd;
property_map<Graph_vvd_MST, edge_weight_t>::type cost;
typedef Traits_vvd::edge_descriptor Edge;
std::vector < Edge > spanning_tree;
int main() {
    Graph_vvd_MST g;
    add_vertex(g);//0 th index vertex
    add_vertex(g);// 1 index vertex
    add_vertex(g);// 2 index vertex
    cost = get(edge_weight, g);
    //Add directed arcs
    for(int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++) {
            if (i == j)
                continue;
            std::pair<Traits_vvd::edge_descriptor, bool> AE = add_edge(i, j, g);
            assert(AE.second);
            if (i == 0 && j == 1)               cost[AE.first] = 1;
            if (i == 0 && j == 2)               cost[AE.first] = 2;
            if (i == 1 && j == 0)               cost[AE.first] = 1;
            if (i == 1 && j == 2)               cost[AE.first] = 2;
            if (i == 2 && j == 0)               cost[AE.first] = 1;
            if (i == 2 && j == 1)               cost[AE.first] = 2;
        }
    kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));
    printf("MST Solution:\n");
    for (std::vector < Edge >::iterator ei = spanning_tree.begin();
        ei != spanning_tree.end(); ++ei) {
        int fr = source(*ei, g);
        int to = target(*ei, g);
        double cst = cost[*ei];
        printf("[%d %d]: %f \n", fr, to, cst);
    }
    getchar();
}

上面的代码生成以下双向图：

代码正确输出：

MST Solution:
[0 1]: 1.000000
[2 0]: 1.000000

是不是文档没有更新，在最近的boost版本中，该算法实际上可以使用有向图？

Answer 1

我会简化代码 Live

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <iostream>

using Graph =
    boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
                        boost::no_property,
                        boost::property<boost::edge_weight_t, double>>;

using Edge = Graph::edge_descriptor;

int main()
{
    Graph g(3); // 0..2

    /*auto [it, ok] =*/ add_edge(0, 1, {1}, g);
    add_edge(0, 2, {2}, g);
    add_edge(1, 0, {1}, g);
    add_edge(1, 2, {2}, g);
    add_edge(2, 0, {1}, g);
    add_edge(2, 1, {2}, g);

    auto cost = get(boost::edge_weight, g);
    std::vector<Edge> spanning_tree;
    kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));

    std::cout << "MST Solution:\n";
    for (auto e : spanning_tree) {
        std::cout << e << ": " << cost[e] << "\n";
    }
}

如果坚持循环插入边：Live

for (auto [i, j, c] : { std::tuple //
         {0, 1, 1.},
         {0, 2, 2.},
         {1, 0, 1.},
         {1, 2, 2.},
         {2, 0, 1.},
         {2, 1, 2.},
     })
{
    if (!add_edge(i, j, {c}, g).second)
        return 255;
}

问题

如果您不满足记录的 pre-conditions 输出是未指定的。未指定并不意味着它会抛出异常（即 specified）。它甚至可能不小心（似乎）做了正确的事情。

关键是该算法的运行假设边缘 - 根据定义 - 可以以相同的成本反向遍历。一旦偏离，算法可能会给出不正确的结果。事实上，某些算法可能会表现出 未定义的行为（例如，带有一些负权重的 Dijkstra 可能永远不会完成）。

你最好

要么将你的图转换为无向图
满足无向图的不变量并验证算法是否正确工作
使用 MDST（最小有向生成树）算法，参见例如Finding a minimum spanning tree on a directed graph

Boost Kruskal 最小生成树算法——无向图与有向图文档

Boost Kruskal minimum spanning tree algorithm -- undirected vs directed graph documentation

c++

boost

boost-graph

问题