0

我一直在尝试使用 prim 方法计算最小生成树，但我对在这种情况下使用权重的方式感到相当困惑。源文档中建议的示例程序似乎不正确，我不明白为什么需要计算边缘介数。请看下面的程序，它旨在制作一个简单的无向图。

#include <igraph.h>
int main()
{
    igraph_vector_t eb, edges;
    igraph_vector_t weights;
    long int i;
    igraph_t theGraph, tree;
    struct arg {
    int index;
    int source;
    int target;
    float weight;
    };
    struct arg data[] = {
    {0, 0, 1, 2.0},
    {1, 1, 2, 3.0},
    {2, 2, 3, 44.0},
    {3, 3, 4, 3.0},
    {4, 4, 1, 2.0},
    {5, 4, 5, 9.0},
    {6, 4, 6, 3.0},
    {6, 6, 5, 7.0}
    };

    int nargs = sizeof(data) / sizeof(struct arg);
    igraph_empty(&theGraph, nargs, IGRAPH_UNDIRECTED);

    igraph_vector_init(&weights, nargs);
    // create graph
    for (i = 0; i < nargs; i++) {
    igraph_add_edge(&theGraph, data[i].source, data[i].target);
    // Add an weight per entry
    igraph_vector_set(&weights, i, data[i].weight);
    }

    igraph_vector_init(&eb, igraph_ecount(&theGraph));
    igraph_edge_betweenness(&theGraph, &eb, IGRAPH_UNDIRECTED, &weights);
    for (i = 0; i < igraph_vector_size(&eb); i++) {
    VECTOR(eb)[i] = -VECTOR(eb)[i];
    }

    igraph_minimum_spanning_tree_prim(&theGraph, &tree, &eb);
    igraph_write_graph_edgelist(&tree, stdout);

    igraph_vector_init(&edges, 0);
    igraph_minimum_spanning_tree(&theGraph, &edges, &eb);
    igraph_vector_print(&edges);
    igraph_vector_destroy(&edges);

    igraph_destroy(&tree);
    igraph_destroy(&theGraph);
    igraph_vector_destroy(&eb);
    return 0;
}

任何人都可以看到这个程序有什么问题吗？它旨在构建一个简单的图表，我希望这是使用权重参数的正确方法。源和目标之间的每条边一个值。

4

1 回答 1

0

关于添加边缘介数的部分来自使用 prim 的原始代码示例。只需要删除它，程序才能使用用户提供的重量值正常工作。

于 2016-04-01T08:28:13.240 回答