用一些边提升最小生成树 included/excluded

Question

我正在尝试按照成本递增的顺序实现图的所有可能生成树的列表。我正在使用 Sorensen and Janssens (2005) 的算法。图初始化如下：

typedef property<edge_weight_t, int> EdgeWeightProperty;
typedef adjacency_list<vecS, vecS, undirectedS, no_property, EdgeWeightProperty> Graph;
typedef Graph::edge_descriptor Edge;
typedef Graph::vertex_descriptor Vertex;
typedef boost::graph_traits<Graph>::edge_iterator EdgeIterator;
typedef std::pair<EdgeIterator, EdgeIterator> EdgePair;
Graph g;

add_edge(1, 2, 3, g);
add_edge(1, 3, 1, g);
add_edge(1, 4, 2, g);
add_edge(2, 3, 3, g);
add_edge(2, 4, 1, g);

在此之后，有必要找到一个图的最小生成树，但有一些限制，例如 Edge(2)-(4) 不应该在 MST 中，而 Edge(1)-(2) 应该在那里.

对于边排除，可以使用 remove_edge_if(..) 从图中删除边。

template<typename WMap>
class Remover
{
public:
    Remover(const WMap& weights, int threshold)
        : m_weights(weights), m_threshold(threshold) {}

    template<typename ED>
    bool operator()(ED w) const { return m_weights[w] <= m_threshold; }

private:
    const WMap& m_weights;
    int         m_threshold;
};

....
// remove edges of weight < 1
Remover< property_map<Graph, edge_weight_t>::type> r(get(edge_weight, g), 1);
remove_edge_if(r, g);
....
std::list < Edge > spanning_treeT;
kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_treeT));

但是如何确保其中一条边始终在生成树中呢？我只是想在 Kruskal 函数的输出中添加一些 Edge，但它显然不起作用。它产生图的 MST + 添加的边：

std::list < Edge > spanning_tree_g2;
Vertex u, v;
EdgePair ep = edges(g2);
u = source(*ep.first, g2);
v = target(*ep.first, g2);
Edge ed = edge(u, v, g2).first;
spanning_tree_g2.push_front(ed);
kruskal_minimum_spanning_tree(g2, std::back_inserter(spanning_tree_g2));

是否有可能以 Kruskal 算法知道包含哪些内容和不包含哪些内容的方式标记边缘？

Answer 1

看来你可以通过分割这条边并在中间插入两个 "artificial" 顶点来强制包含某条边。

已经需要 MST 算法来生成覆盖所有顶点的边树。

因为人工顶点是您有意添加的，所以很容易确保使用任何其他边永远无法到达它。

之前：

   ------------------[e:w1+w2]------------------

之后：

   ----[e1:w1]---(v1)---[em:0]---(v2)---[e2:w2]----

（其中v1和v2是插入的顶点）。

在你 "collapse" 任何 (e1,em,e2) 或 (e2,em,e1) 的序列变成 (e) 之后。

您最终可能会得到一棵到达 v1 和 v2 但从未遍历 em 的树。在这种情况下，您可以简单地删除 e1 和 e2 之一并无条件地用 e 替换它。

用一些边提升最小生成树 included/excluded

Boost minimum spanning tree with some edges included/excluded

boost

graph

minimum-spanning-tree

boost-graph

kruskals-algorithm