1

我正在尝试按照成本增加的顺序来实现图的所有可能生成树的列表。我正在使用Sorensen 和 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 算法知道包含什么和不包含什么的方式标记边缘？

4

1 回答 1

0

我似乎可以通过分割这条边并在中间插入两个“人造”顶点来强制包含某个边。

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

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

前：

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

后：

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

（插入顶点的位置v1和位置）。v2

在你“折叠”任何序列(e1,em,e2)或.(e2,em,e1)(e)

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

于 2015-06-22T14:41:05.847 回答