2

我正在使用 igraph 库在 C 中工作。

我需要使用以下调用计算图的最小生成树:

igraph_minimum_spanning_tree_prim( &input_graph, &mst_tree, &w); 

在哪里:

  • input_graph:要处理的图。是igraph_t类型。
  • mst_tree:函数返回的 mst 树。是igraph_t类型。
  • w: input_graph图每条边的权重向量。是igraph_vector_t类型。

按照 igraph 库中的要求,边和权重之间的关联由它们的索引给出,即 input_graph中的第一条边的权重由w向量的第一个元素给出,第二条边的权重由下式给出w向量的第二个元素,以此类推。

由于 mst_tree 的边是input_graph边 的子集 (因此, input_graph 和 mst_tree 中的边数量不同因此无法通过关联它们的索引来获得mst_tree的边权重。

有一些 igraph 函数可以获取 mst_tree 中每条边的权重只知道mst_treeinput_graph和 w?

吉列尔莫。

4

1 回答 1

1

在 igraph 0.5.4 中,没有这样的函数,抱歉 :( 在 igraph 0.6 中,最小生成树 API 将发生一些变化,因此将有另一个具有以下签名的函数:

int igraph_minimum_spanning_tree(const igraph_t* graph, igraph_vector_t* res, const igraph_vector_t* weights);

whereres将包含构成生成树的边的索引。igraph 0.6 尚未发布,但它相当稳定,因此您可能想尝试升级到 igraph 0.6(如果您不介意这里和那里的一些 API 更改)。

免责声明:我是 igraph 的作者之一。

于 2011-08-08T13:28:22.410 回答